[pro] 프로그래머스 level3 12907 거스름돈 (Java) - dp

[문제]

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

프로그래머스

 

[풀이]

1원, 2원, 5원이 있고 5원의 거스름돈을 거슬러줘야하는 상황.

1원 - 1 (1가지)

2원 - 1+1, 2 (2가지)

3원 - 1+1+1, 1+2 (2가지)

4원 - 1+1+1+1, 1+1+2, 2+2 (3가지)

5원 - 1+1+1+1+1, 1+1+1+2, 1+2+2, 5 (4가지)

 

즉 거스름돈 5원을 거슬러주기 위한 경우의 수는 다음과 같다.

1) 1원을 이용 (1+1+1+1+1)

2) 2원을 이용. 5-2=3원. (1+1+1+2, 1+2+2)

3원을 거슬러주기 위한 경우의 수는? 2가지.

2-1) 1원을 이용 1가지 (1+1+1)

2-2) 2원을 이용 1가지 (1+2)

3) 5원을 이용 (5)

 

따라서 dp[i] = k, i원의 거스름돈을 낼 수 있는 경우의 수 k에 대해서 처음 money[0]원을 이용해서 낼 수 있는 경우의 수를 초기화해 놓는다.

다음으로 money[1]~money[money.length]의 모든 돈을 이용해가며 (계산된 경우의 수+money[i]를 이용해서 낼 수 있는 경우의 수)를  구한다.

 

[코드]

 

import java.util.*;

class Solution {
    public int solution(int n, int[] money) {
        int answer = 0;
        //Finn이 n 원을 거슬러 줄 방법의 수를 return
        Arrays.sort(money);
        
        //dp[i] = k, i원의 거스름돈을 낼 수 있는 경우의 수 k
        int[] dp = new int[n+1];
        for(int i=0; i<=n; i++){
            if(i%money[0]==0){
                dp[i] = 1; //money[0]만으로 낼 수 있는 경우 
            }
        }
        
        //2 5
        for(int i=1; i<money.length; i++){
            //이미 계산된 경우 + money[i]원을 이용해서 거스름돈을 낼 수 있는 경우
            for(int j=money[i]; j<=n; j++){
                dp[j] += dp[j-money[i]];
            }
        }
        
        answer = dp[n];
        return answer;
    }
}