programmers. 거스름돈

문제

링크

코딩테스트 연습 - 거스름돈

풀이

dp를 사용하여 풀 수 있는 문제

N : 5, money : [1, 2, 5]

	0	1	2	3	4	5
1
2
5

위의 표에서 세로 첫 줄은 낼 수 있는 돈의 종류, 가로 첫 줄은 거슬러 주어야할 금액이다

1원으로 0원, 1원, 2원, 3원, 4원, 5원을 낼 수 있는 경우의 수는 각각 1가지 밖에 없다

	0	1	2	3	4	5
1	1	1	1	1	1	1
2
5

그 다음 1원과 2원을 이용해서 경우의 수를 구해야한다

	0	1	2	3	4	5
1	1	1	1	1	1	1
2	1	1	2	2	3	3
5

0원 :

1*0 + 2*0 = 0

->1개

1원 : 1*1 + 2*0 = 1

->1개

2원 :

1*2 + 2*0 = 2,

1*0 + 2*1 = 2

-> 2개

3원 :

1*3 + 2*0 = 3,

1*1 + 2*1 = 3

-> 2개

4원 :

1*4 + 2*0 = 4,

1*2 + 2*1 = 4,

1*0 + 2*2 = 4

-> 3개

5원 :

1*5 + 2*0 = 5,

1*3 + 2*1 = 5,

1*1 + 2*2 = 5

-> 3개

여기서 dp로 설계할 수 있는 규칙을 발견할 수 있는데

1원과 2원으로 5원을 만들기 위한 경우의 수 = 3원을 만들 수 있는 경우의 수 + 1원으로 5원을 만들 수 있는 경우의 수 가 된다

1원과 2원으로 3원을 만들기 위한 경우의 수 = 1원을 만들 수 있는 경우의 수 + 1원으로 3원을 만들 수 있는 경우의 수

	0	1	2	3	4	5
1	1	1	1	1	1	1
2	1	1	2	2	3	3
5	1	2	2	2	3	4

i = money.length, j = n+1 이라고 했을 때 이 표를 이차원 배열로 나타내면 arr[i][j]가 되고

규칙은 arr[i][j] = arr[i][j-돈의 종류] + arr[i-1][j]; 로 표현할 수 있다

        const dp = Array(money.length).fill().map(()=>Array(n+1).fill().map((_,i)=>i%money[0] ? 0 : 1));

        for(let i=1; i<dp.length;i++){
            for(let j=0; j<n+1;j++){
                if((j-money[i]) >= 0) {
                    dp[i][j] = dp[i][j-money[i]]%MOD + dp[i-1][j]%MOD;
                    continue;
                }
                dp[i][j] = dp[i-1][j]%MOD;
            }
        }

위의 식을 활용하여 코드를 짜면 이런식으로 나오게 되지만 효율성 테스트를 통과하지 못한다

for(let j=0; j<n+1;j++)문을 도는 과정을 자세히 보면 j가 money[i] 보다 작을 경우에는 dp[i-1][j]에서 값을 그대로 내려 받는 것을 볼 수 있는데

이런 경우에는 굳이 2차원 배열이 아니라 1차원 배열로 표현해서 효율성을 높일 수 있다

코드

function solution(n, money) {
    var answer = 0;

    const MOD = 1000000007;

    money.sort((a, b) => a-b);

    const dp = Array(n+1).fill().map((_,i)=>i%money[0] ? 0 : 1);

    for(let i=1;i<money.length;i++){
        for(let j=0;j<dp.length;j++){
            if(j-money[i] >= 0) dp[j] = dp[j]%MOD+ dp[j-money[i]]%MOD;
        }
    }

    return dp[dp.length-1]%MOD;
}