[Algorithm] programmers-12907-거스름돈.java

/*dp?*/
class Solution {
    public int solution(int n, int[] money) {
        long[] dp = new long[n+1];

        //초기화
        dp[0] = 1;

        for(int i=0;i<money.length;i++){
            int currency = money[i];
            for(int j = currency;j<=n;j++){
                dp[j] += dp[j-currency]; 
            }
        }

        /* 
        중복까지 세버리는 코드. 예를들어 money = [1,2,5] 일때 n=3 이라면
        (1,2) (2,1)이 중복으로 세어져서 답이 1인데 2가 되어버린다.
        */
        // for(int i=0;i<=n;i++){
        //     for(int j=0;j<money.length;j++){
        //         int currency = money[j];
        //         if(i-currency > 0){
        //             dp[i] += dp[i-currency];
        //         }
        //     }
        // }

        int answer = (int)(dp[n] % 1000000007);
        return answer;
    }
}

• 처음에 볼 때 dp를 떠올렸다. 여기까진 ok지만... 중복까지 세어버려서 예제의 답이 9가 나와버렸다.

• 어떻게 할까 고민을 하던중에 떠올린 방법이 다행히 맞았다.

• 우선 dp배열을 만든다. 그리고 money배열의 통화(currency)하나씩 고려하는 것이다.

  • 문제의 예시를 통해 알아보면 money = [1,2,5]이고 n=5니까 money가 1일때 dp[j] += dp[j-currency]; 점화식에 대입하면 나보다 1원 적은 경우의 수를 현재 dp[j]에 누적시키는 것.

  • n=2일때를 살펴보면 dp[j] += dp[j-2] 를 해주면된다. j의 경우의 수에 j보다 2원 적은 경우의 수를 더해주는 것이다. 그러면 1원짜리를 사용한 거스름돈 경우의 수와 2원짜리를 사용한 거스름돈 경우를 합친 것 까지 계산된다.

  • n=5 일때도 마찬가지로 dp[j] += dp[j-5]를 누적시킨다.