[프로그래머스 Lv3][자바] 거스름돈

❓문제설명

거스름돈

프로그래머스

 

---

🔍문제해석

어떤걸 풀어야 할까?

• 잔돈 금액과 화폐종류가 주어지면 화폐들을 이용해 잔돈을 거슬러 줄 수 있는 모든 방법을 구해라
• 너무 큰 수가 나올 수 있으니 1,000,000,007을 나눈 나머지를 반환하라.

---

🧐문제풀이

• 문제 풀이 구상

배열을 만들고 칸마다 해당 인덱스의 금액을 만들기 위해서는 몇개의 방법이 있는지 담는다.

그 계산이 모두 끝난 후 배열[잔돈] 의 값을 정답으로 리턴한다.

방법의 갯수를 찾기 위해서는 아래와 같이 생각해보았다.

오름차순으로 화폐 한개씩 계산을 해본다.

 

(기존 화폐들로 계산된 i금액을 만드는 갯수) +  (i 금액을 계산할때 coin을 사용하게 될 경우 => i-coin 금액을 만드는 갯수)

dp[i] = dp[i] + dp[i-coin];

 

• 1원 동전:
  • dp[1] = dp[0] + 0 (1원 만들기) = 1 // 1원 동전만 써서 만들수 있으므로 1개
  • dp[2] = dp[1] + 0 (2원 만들기) = 1
  • dp[3] = dp[2] + 0 (3원 만들기) = 1
  • dp[4] = dp[3] + 0 (4원 만들기) = 1
  • dp[5] = dp[4] + 0 (5원 만들기) = 1
• 2원 동전:
  • dp[2] = dp[0] + 1 (2원 만들기) = 2 // 1+1, 2 1원과 2원을 이용한 방법이 있으므로 2개
  • dp[3] = dp[1] + 1 (3원 만들기) = 2
  • dp[4] = dp[2] + 1 (4원 만들기) = 3 // 1 + 1+ 1+ 1, 1+1+2, 2+2 => 3개
  • dp[5] = dp[3] + 1 (5원 만들기) = 3
• 5원 동전:
  • dp[5] = dp[0] + 1 (5원 만들기) = 4

 

• 알고리즘 선택

금액을 만들기 위해 동전의 조합을 고려하는 문제는 전형적인 DP 문제..!

 

---

！제출코드

1. n금액을 조합할 수 있는 방법을 배열에 구해야하기 때문에 오류가 생기지 않도록 n+1 길이의 배열을 생성한다.
2. dp 문제는 처음으로 계산되는 기본값의 설정이 중요하다고 생각한다. 까먹지 말고 1로 설정(0을 만드는 방법은 하나. 아무 동전도 사용하지 않는다.)
3. 화폐단위로 반복문을 실행한다.
4. 화폐단위부터 방법갯수 계산을 시작한다면 dp[i]  대입시에 더 작은 개수 대입에 대한 것을 방지할 수 있다.
5. i 금액을 위해 화폐들을 조합하는 방법을 구한다. 너무 큰 수가 생길 수 있으니 1,000,000,007을 나누어 나머지를 구하자
6. 최종적으로 인덱스 n에 있는 항목을 정답에 대입한다.

class Solution {

       public static int solution(int n, int[] money) {
       
       // (1)
        int [] dp = new int[n+1];
       // (2) 
        dp[0] = 1; // 금액 0을 만드는 방법은 1(아무동전도 사용하지 않는다.)
        
       // (3)
        for(int coin : money) {
            // (4)
            for(int i = coin; i <= n; i++) {
               // (5)
                dp[i] = (dp[i] + dp[i-coin]) % 1000000007;
            }
        }
        // (6)   
        int answer = dp[n];
        return answer;
    }
}