Dynamic Programming(냅색 알고리즘-1)

동전교환(냅색 알고리즘)

 

다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가?

 각 단위의 동전은 무한정 쓸 수 있다.

입력설명

첫번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음 줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.

각 동전의 종류는 100원을 넘지 않는다.

출력설명

첫번째 줄에 거슬러 줄 동전의 최소 개수를 출력한다.

입력예제 1

3

1 2 5

15

 

출력 예제 1

3

 

 

만약 동전의 종류가 너무 많고, 거슬러 줄 돈 또한 너무 많으면 DFS(재귀)형식으로는 풀 수 없다는 것을 판단해야한다.

바로 동적계획법을 사용해야한다.

 

먼저 dy배열을 선언해주고 우리는 배열의 크기를 거슬러줄 돈의 값으로 정해줄 것이다.

 

이 배열은 0이 아닌 큰 숫자로 초기화 해야한다. (최솟값을 넣을 것이기 때문에) 

이제 dy[i]에 들어갈 값이 무엇을 의미하는 지 알아야한다.

☝ dy[i]에는 i금액을 거슬러주는데 사용된 최소 동전의 의 갯수가 들어간다.

 

처음에는 1원짜리 하나만 있을 때를 가정하고 dy[i]를 채워간다.

이때 우리는 무작정 값을 넣는게  아닌

dy[i-coin[0]]+1 을 넣어야한다.

이는 현재 dy[i]에 동전 1원을 넣기전에 그 전에 1원을 넣은 값에 +1을 해서 갯수를 채운 것이다.

 

이 말은 즉 만약 dy[5]원을 거슬러준다고 가정할 때 

 먼저 5원에서 1원을 뺀 dy[4]원의 값을 가져온다. -> 1원 하나만 사용할 것이므로

현재 dy[4]원의  값은 1원으로 거슬러줄 수 있는 최소 갯수가 저장되어있는 상태다.

그 값에 1원 하나만 추가하면 dy[5]원은 현재 1원으로 거슬러 줄 수 있는 최소 동전의 갯수를 가진 것이다.

 

이러한 방식으로 일단 1원일 때를 배열로 채운다.

 

이제 2원짜리를 적용해서 배열에 채울 것이다.

2원짜리 하나만 무조건 사용한다고 가정하는 것이다.

이 때 중요한 것은 거슬러줄 금액을 직접 2원을 빼는 것이 아니고

dy[i-2원]+1을 해서 값을 넣는 것이다.

 

 

이제 5원짜리를 적용해서 배열에 채울 것이다.

5원짜리 하나만 무조건 사용한다고 가정하는 것이다.

그럼 위와 같이 dy[15]에 최소 동전의 갯수가 들어가게 된다.

 

 

이제 코드로 구현해보자

 

let coin=[1,2,5];
let N =15;
let dy=Array(N+1).fill(100000);
dy[0]=0;
for(vari=0;i<coin.length;i++){
	for(var j=1;j<=N:j++){
        dy[j]=Math.min(dy[j],dy[j-coin[i]]+1);
    }
}
console.log(dy[N]);