[12907] 거스름돈

✔ 거스름돈

[프로그래머스 12907]

문제 분석하기

다이나믹 프로그래밍을 이용해 특정 거스름돈을 거스를 수 있는 경우의 수를 저장하여 이를 이용하도록 함

 

예) money = [1, 2, 5]

	0원	1원	2원	3원	4원	5원
1원 (동전 1개)	1	1 (현재 동전 사용 O 1)	1 (현재 동전 사용 O 1)	1 (현재 동전 사용 O 1)	1 (현재 동전 사용 O 1)	1 (현재 동전 사용 O 1)
1, 2원 (동전 2개)	1	1 (현재 동전 사용 X 1)	2 (현재 동전 사용 X 1 + 현재 동전 사용 O 1)	2 (현재 동전 사용 X 1 + 현재 동전 사용 O 1)	3 (현재 동전 사용 X 1 + 현재 동전 사용 O 2)	3 (현재 동전 사용 X 1 + 현재 동전 사용 O 2)
1, 2, 5원 (동전 3개)	1	1 (현재 동전 사용 X 1)	2 (현재 동전 사용 X 2)	2 (현재 동전 사용 X 2)	3 (현재 동전 사용 X 3)	4 (현재 동전 사용 X 3 + 현재 동전 사용 O 1)

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[i][j]는 i개의 동전으로 j원을 만들 수 있는 경우의 수
2. 점화식을 구함
   • j가 0일 경우 0원을 만들 수 있는 경우의 수는 1개 이므로
     D[i][0] = 1
   • D[i][j]는 현재 동전을 사용하지 않고 j원을 만드는 경우의 수와 현재 동전을 사용하여 만드는 경우의 수의 합이므로
     D[i][j] = D[i - 1][j] + D[i][j - money[i - 1]] % 1000000007
     
   • 만약 현재 동전이 j원보다 클 경우에는 사용할 수 없으므로 현재 동전을 사용하지 않고 j원을 만드는 경우의 수만 구하므로
     D[i][j] = D[i - 1][j] % 1000000007
3. 점화식으로 D 배열을 채운 후 D[money의 길이][n]의 값을 반환

슈도코드 작성하기

n(거슬러 줘야 하는 금액)
money(현재 보유하고 있는 돈의 종류)
D(i개의 동전으로 j원을 만들 수 있는 경우의 수)
for(i -> 1부터 money의 길이까지) {
    for(j -> n + 1까지) {
        if(j가 0이라면)
            0원을 만들 수 있는 경우의 수는 1개 이므로 D[i][j] = 1
        else {
            if(j가 money[i - 1]보다 작다면)
                현재 동전을 사용할 수 없으므로 현재 동전을 사용하지 않고 j원을 만드는 경우의 수만 구하므로 
                D[i][j] = D[i - 1][j] % 1000000007
            else
                현재 동전을 사용하지 않고 j원을 만드는 경우의 수와 현재 동전을 사용하여 만드는 경우의 수의 합이므로
                D[i][j] = D[i - 1][j] + D[i][j - money[i - 1]] % 1000000007
        }
    }
}
D[money의 길이][n]을 반환

코드 구현하기

/**
 * 12907) 거스름돈
 */
public class L008_12907 {
    // n(거슬러 줘야 하는 금액)
    // money(현재 보유하고 있는 돈의 종류)
    public int solution(int n, int[] money) {
        // D(i개의 동전으로 j원을 만들 수 있는 경우의 수)
        int[][] D = new int[money.length + 1][n + 1];
        // 1개의 동전부터 money의 길이의 동전까지
        for (int i = 1; i <= money.length; i++) {
            // 0원부터 n + 1원까지
            for (int j = 0; j < n + 1; j++) {
                // j가 0이라면
                if (j == 0)
                    // 0원을 만들 수 있는 경우의 수는 1개
                    D[i][j] = 1;
                else {
                    // j가 money[i - 1]보다 작다면
                    if (j < money[i - 1])
                        // 현재 동전을 사용할 수 없으므로 현재 동전을 사용하지 않고 j원을 만드는 경우의 수만 구하도록 함
                        D[i][j] = D[i - 1][j] % 1000000007;
                    else
                        // 현재 동전을 사용하지 않고 j원을 만드는 경우의 수와 현재 동전을 사용하여 만드는 경우의 수의 합을 구하도록 함
                        D[i][j] = (D[i - 1][j] + D[i][j - money[i - 1]]) % 1000000007;
                }
            }
        }
        // D[money의 길이][n]을 반환
        return D[money.length][n];
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L008_12907 solution = new L008_12907();

        int n = 5;
        int[] money = { 1, 2, 5 };

        int result = solution.solution(n, money);

        System.out.println(result);
    }
}