[인프런 자바/java] 5. 동전교환(냅색 알고리즘) _디버깅의 눈물

체크 포인트

 

1. 다이나믹 프로그래밍(Dynamic Programming, 동적계획법)을 이용

 

-큰 문제를 여러 가지 작은 문제로 나누어 해결해보는 DP를 이용했다.

-예시 1의 예를 들면, 3종류의 동전(1원, 2원, 5원)으로 15원을 만드는 최소의 동전개수를 구해야 한다.

 

-동적 계획법에 따라, 작은 문제로부터 큰 문제에 대한 해결을 추론해 보았다.

 

1) 1원에서부터 15원까지

 

(1)1원,

(2)1원+2원,

(3)1원+2원+5원 

 

세 가지 경우로 나누고, 구성할 수 있는 동전의 최소 개수를 구하며 규칙성을 찾아보았다. 해당 규칙성을 찾기 위해 M=0일 때는 동전의 종류에 상관없이 0을 입력했다.

 

(1)1원을 이용한 동전의 최소 개수

 

M	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

 

-1원으로 구성할 수 있는 동전의 최소 개수는 M과 동일하다.

 

 

 

(2)1원과 2원을 이용한 동전의 최소 개수

 

M	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원 + 2원	0	1	1 0+1	2 1+1	2 1+1	3 2+1	3 2+1	4 3+1	4 3+1	5 4+1	5 4+1	6 5+1	6 5+1	7 6+1	7 6+1	8 7+1

 

-M이 1일 때는, 2원짜리 동전을 사용할 수 없기 때문에 그대로 1로 유지한다. 

 

-M이 2 이상일 때부터 2원을 사용할 수 있기 때문에 비교를 하며 최소 개수를 구해야 한다.

-M=2일 때, 동전 합이 M=0일 때 최소 개수(0)에 2원을 더하면(1) 최소 개수 1개가 된다.

-M=3일 때, 1원까지의 최소 개수(1)에 2원을 더하면(1) 최소 개수 2개가 된다.

-M=4일 때, 2원까지의 최소 개수(1)에 2원을 더하면(1) 최소 개수 2개가 된다.

...

-M=15일 때, 13원까지의 최소 개수(7)에 2원을 더하면(1) 최소 개수 8개가 된다.

 

dp[i] = dp[i-coins[j]] + 1

 

예시로부터 위의 식을 추론할 수 있다.

 

하지만 위의 식은 항상 성립하는 것이 아니다.

만약 동전이 1원, 6원, 9원 세 종류가 있고, 12원의 거스름돈을 만드는 상황이라고 가정하자. 실제 최소의 개수는 2개(6+6)이지만, 위의 식대로만 진행한 경우 최소의 개수는 4개 (1+1+1+9)가 되어버린다. 

 

dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);

 

따라서 위의 식에 최소 개수를 비교해주는 조건을 추가해야 한다. 이를 토대로 5원까지 추가한 경우 아래와 같은 식을 구할 수 있다.

 

 

(3)1원과 2원과 5원을 이용한 동전의 최소 개수

 

M	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1원 + 2원	0	1	1	2	2	3	3	4	4	5	5	6	6	7	7	8
1원 + 2원 + 5원	0	1	1	2	2	1	2	2	3	3	2	3	3	4	4	3

 

 

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {
	// 동전의 종류를 담는 배열 
	static int[] coins;
	// 동전합을 이루는 최소의 개수를 담는 배열 
	static int[] dp;
	// 동전 종류의 개수, 동전의 최소 개수 변수 
	static int N,count;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	// 동전의 종류 변수 
    	N = Integer.parseInt(st.nextToken());
    	// 동전의 종류를 담아줄 배열 선언 
    	coins = new int[N];
    	
    	st = new StringTokenizer(br.readLine(), " ");
    	
    	// 동전 종류 담기 
    	for(int i=0; i<N; i++){
    		coins[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	// 거슬러 줄 금액 
    	int M = Integer.parseInt(br.readLine());
    	
    	// 동전의 최소 개수를 담는 배열 초기화 
    	dp = new int[M+1];
    	// 0번째를 0으로 초기화 
    	dp[0] = 0;
    	
    	
    	// 탐색 시작 
    	solution(M);
    	
    } // end of Main
    
    
    static void solution(int M) {
    	
    	for(int i=1; i<=M; i++){
    		// 배열의 각 자리에 들어갈 동전의 최소개수를 초기화 
    		dp[i] = Integer.MAX_VALUE;
    	}

    	// 각 종류의 동전 별 탐색,
		for(int j=0; j<N; j++){
			
			// 0번째 동전부터, 거슬러 줄 금액을 만들 수 있는 동전의 최소 개수 탐색 
			for(int i=coins[j]; i<=M; i++){
    		
				// 거슬러줄 동전의 최소 개수 dp[i]는 
				// 기존의 dp[i]와,
				// coins[j] 동전을 사용한 dp[i-coins[j]]+1 중에 최소값으로 한다.
				dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
    		}
    	}
    	
    	System.out.println(dp[M]);
    	
    } // end of solution
    
} // end of Main