거스름돈 : https://school.programmers.co.kr/learn/courses/30/lessons/12907
Problem
Solve
완탐, 백트래킹.. 여러 방법을 생각해봤지만 명쾌한 답이 나오지 않아 다른 분의 풀이에서 힌트를 얻었습니다.
DP도 생각은 했었지만 접근 방법을 생각을 못했었지만 힌트를 통해 접근할 수 있었습니다.
접근 방법은 아래와 같습니다.
먼저 거스름돈과 소지하고 있는 돈(money)을 기준으로 테이블을 만듭니다.
table의 각각은 현재 money와 이전 money로 현재 거스름돈을 낼 수 있는 경우의 수라고 생각하면됩니다.
table[0][j]은 1, table[1][j]은 1과 2, table[2][j]는 1,2,5로 놓고 거스름돈을 낼 수 있는 경우의 수를 만들어 봅니다.
우선 table[0][j]는 '1'의 돈으로 거스름돈을 낼 수 있는 경우의 수를 구합니다.
1의 돈으로 각 거스름돈은 모두 1개의 경우의 수로 만들 수 있기 때문에 1로 갱신해줍니다.
table[i][0]은 무슨값이냐고요?
일단은 손으로는 이렇게 만들수 있으니 다음 케이스에서 점화식과 함께 설명하겠습니다.
그 다음, table[1][j]는 '1'과'2'의 돈으로 각 거스름돈을 만들수 있는 경우를 구합니다.
table[1][2]의 경우 2의 거스름돈은 '1'과'2'의 돈으로 1,1, 2로 총 2개의 방법으로 거스름돈을 줄 수 있습니다.
그렇다면 1의 돈으로 거스름돈을 주는 경우(1,1)는 table[0][2]에서 구할 수 있습니다.
그리고 2의 돈으로 거스름돈을 주는 경우(2)는 table[1][0]에서 구할 수 있습니다.
즉, table[i][0]은 현재 money로만 거스름 돈을 주는 경우의 수입니다.
풀어서 설명하자면, table[i][j]의 경우에서 해당 거스름돈을 주기 위해 해당 money를 제외한 이전의 money로 거스름돈을 주는 경우 (table[i-1][j])와 해당 거스름돈에서 현재 money를 제외하고의 거스름돈을 주는 경우(table[i][j-현재 money])
다른 케이스로 예를 들어서 현재 거스름돈이 5이고 현재 money가 2인 경우 table[1][5]의 경우를 찾아야한다면, 현재 money의 이전 money인 1에서 거스름돈 5를 주는 경우는 1,1,1,1,1으로 1개입니다. 즉, table[0][5]입니다.
그리고 현재 거스름돈 5에서 현재 money 2를 제외한다면 거스름돈 3의 경우를 구해야합니다. 거스름돈 3을 내기 위한 경우는 2,1, 1,1,1으로 2개입니다. 즉, table[1][3]입니다.
table[1][5] = table[0][5] + table[1][3] = 3이 되게 됩니다.
그렇다면 점화식은 table[i][j] = table[i-1][j] + table[i][j-money[i]] 이 되게 됩니다.
table을 완성하게 된다면 아래와 같게 됩니다.
table[2][5]는 table[1][5] + table[2][0]으로 4가 나오게 됩니다.
이를 통해 주어진 money들을 통해 n의 거스름돈을 구할 수 있게 됩니다.
그리고 점화식을 구하면서 발견한점은 각 money와 거스름돈이 동일하기 전까지의 경우는 모두 동일합니다.
현재 money보다 작은 거스름돈은 이전 money의 경우의 수로만 구성할 수 있기 때문입니다.
Code
class Solution {
public int solution(int n, int[] money) {
//첫번째 money에서도 table[i-1][j]가 수행되므로 money의 길이에서 +1을 해주었습니다.
int[][] table = new int[money.length+1][n+1];
table[0][0] = 1;
for(int i=1;i<table.length;i++){
//현재 money이전의 거스름돈 경우 초기화
beforeInit(table, i,money[i-1]);
//현재 money부터 거스름돈을 내는 경우
for(int j=money[i-1];j<=n;j++){
table[i][j] = (table[i-1][j] + table[i][j-money[i-1]])%1000000007;
}
}
//table의 끝 값이 모든 money로 낼 수 있는 경우의 수
int answer = table[money.length][n];
return answer;
}
//현재 money보다 작은 거스름돈은 이전 money들로만 거스름돈을 낼 수 있다.
public void beforeInit(int[][] table, int y, int x){
for(int j=0;j<x;j++){
table[y][j] = table[y-1][j];
}
}
}Result
Reference
