[JS] 거스름돈 (자세한 설명)

까다로운 dp문제였다.

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12907

프로그래머스

 

 

문제에서 보여지는게 dp문제였기 때문에 고민을 많이 해봤다. 

 

dp[n]을 n원을 만들기 위한 경우의 수라고 생각을 해보자.

 

단순하게 생각한다면 5라는 놈을 만들기 위해서 dp[1]*dp[4] +  dp[2]*do[3] 과 같은 조합으로 만들수 있지 않나? 라는 생각을 했다.

 

dp[n] = dp[n-1]*dp[n] + dp[n-2] + dp[n-3] + ... [dp[n-n/2]]가 된다 생각할 수 있다. 예를 들어서 아래와 같이 기본값을 세워둔 후 방금 새운 식대로 해보자.

 

1 -> 1

2 -> 1

3

4

5 -> 1

6

7

 

----------------

1 -> 1

2 -> 1 + 1 = 2

3 ->  1 * 2 = 3

4 -> 1*3 + 2+2 = 7

5 -> 1*7 + 2*3 = 13

 

언뜻봐도 계산이 잘 안되는 것을 알 수 있다. 이 이유는 바로 중복되는 경우가 있기 때문이다.

 

3을 만들때 1 1 1 , 1 2 두가지 경우의 수가 나온다. 2를 만드는 경우가 2가지라 생각했지만 2를 1로 만드는 경우 결국

(1 1 1) , (1 2) , ( 1 , (1,1))  와 같이 나오기 때문이다. 따라서 해당 문제의 경우 이 중복된 수를 어떻게 없애는지가 관건인 문제이다.

 

 

 

이번에는 관점을 바꿔서 돈을 기준으로 생각해보자. dp자체는 이전과 똑같이 둔다.

 

dp[n] = n을 만들 수 있는 경우의 수

 

dp를 채워나가는데 1만사용해서 경우의수를 만들고, 2를 추가해서 경우의 수를 만들고, 5를 추가해서 경우의수를 만들어 보자.

 

먼저 1만 사용한 경우

 

1 -> 1

2 -> 1

3 -> 1

4 -> 1

5 -> 1

6 -> 1

7 -> 1

 

위와 같이 모든 경우의 수가 1씩 나오게 될 것이다.

 

이제 2를 추가해 보자. 즉 1과 2의 코인만 있다고 생각해보자.

 

1 -> 1

2 -> 2

3 -> 2

4 -> 3

5 -> 3

6 -> 4

7 -> 4

 

이제 5를 추가해 보자.

 

1 -> 1

2 -> 2

3 -> 2

4 -> 3

5 -> 4

6 -> 5

7 -> 6

 

 

동전의 값을 c라고 한다면 c라는 동전을 추가할때 c부터 시작해서 1씩 증가하며 dp[i-c] 를 더해가는 것을 알 수 있다.

 

 

 

 

이 부분이 잘 이해가 안된다면 반대로도 생각해보자.

 

1,2 를 활용해서 2가지 경우의 수로 3을 만들었다고 생각해보자. 5라는 코인이 들어온다면 3에 5를 더한 8을 만들때 이 3을 활용할 수 있음을 알 수 있다.

 

따라서 8을 만들때는 [기존에 1,2로 만들던 8의 경우의 수] + [기존에 1,2로  만들던 3의경우의 수] 가 되게 된다.

 

그렇다면 5가 2개 이상 쓰이는 경우는 어떻게 계산하는지 이해가 잘 안될 수 있다.

 

 

예를들어서 13이 들어왔다면

[기존에 1,2로 만들던 13의 경우의 수 ] + [기존에 1,2로 만들던 8의경우의수] + [기존에 1,2로  만들던 3의 경우의수] 가되어야 한다고 생각할 수 있다. 

 

하지만 앞에서부터 dp를 채워왔기 때문에 d[13]을 계산 할때

 

dp[8]에는 이미  [기존에 1,2로 만들던 8의경우의수] + [기존에 1,2로  만들던 3의 경우의수] 값이 들어있게 된다!! 

 

즉, [기존에 1,2로 만들던 13의 경우의 수 ] + dp[8] === [기존에 1,2로 만들던 13의 경우의 수 ] + [기존에 1,2로 만들던 8의경우의수] + [기존에 1,2로  만들던 3의 경우의수]

 

가 성립하게 된다.

 

 

 

function solution(n, money) {
    const dp = Array(n+1).fill(0)
    dp[0] = 1;

    for(const currency of money){
        for(let i = currency; i <= n; i += 1){
            dp[i] += dp[i - currency];
        };
    };
    return dp[n];
    
    
}