[프로그래머스] 거스름돈 - Java

문제

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

프로그래머스

 

---

문제 개요

Finn은 야간 아르바이트 중 손님에게 거슬러 줄 금액 n을 가지고 여러 동전 단위를 이용해 거스름돈을 줄 수 있는 방법의 경우의 수를 계산하려 합니다. 동전의 단위는 여러 가지가 있으며, 각 동전은 무한히 사용할 수 있습니다. 주어진 금액 n을 다양한 동전 조합으로 거슬러 줄 수 있는 경우의 수를 구하는 문제입니다.

접근 방법

이 문제는 동적 계획법(Dynamic Programming, DP)을 이용해 해결할 수 있습니다. 각 동전 단위마다 거슬러 줄 수 있는 경우의 수를 누적 계산하는 방식으로 접근합니다.

1. DP 배열 정의: dp[i]는 i원을 거슬러 줄 수 있는 방법의 수를 저장하는 배열입니다. 초기 상태에서는 dp[0] = 1로 설정합니다. 이는 거슬러 줄 금액이 0일 때, 아무 동전도 사용하지 않는 1가지 방법이 존재한다는 것을 의미합니다.
2. 동전 단위별 경우의 수 계산: 각 동전에 대해, 그 동전으로 거슬러 줄 수 있는 금액을 확인하고, dp 배열을 갱신해 나갑니다. 이를 위해 외부 반복문에서는 동전 단위를 순회하고, 내부 반복문에서는 해당 동전으로 만들 수 있는 금액부터 시작해 DP 배열을 업데이트합니다.
3. 누적 계산: 동전이 추가될 때마다, 이전 동전으로 만들 수 있었던 금액에 현재 동전 단위를 더해 나가며 방법의 수를 누적합니다.
4. MOD 연산 적용: 결과가 매우 클 수 있으므로, 매 단계에서 1,000,000,007로 나눈 나머지를 저장하여 최종 값을 반환합니다.

 

숫자 coin을 사용해 목표값 target을 만드는 경우의 수를 계산하는 과정인데, 각 동전(숫자)을 하나씩 차례로 추가하면서 dp 배열을 업데이트합니다.

1. for (int coin : coins) 부분:

이 반복문은 주어진 숫자들(1, 2, 5)을 순차적으로 선택합니다. 즉, 먼저 숫자 1을 사용하여 모든 경우의 수를 계산하고, 그 다음 숫자 2를 사용해 추가적인 경우의 수를 고려하고, 마지막으로 숫자 5를 사용하여 남은 경우의 수를 고려하는 방식입니다.

2. for (int i = coin; i <= target; i++) 부분:

이 반복문은 선택된 coin(숫자)으로 목표 숫자를 만들 수 있는 모든 가능한 값을 확인합니다. 여기서 i는 현재 만들고자 하는 목표 값입니다. 예를 들어, 숫자 1을 사용할 때 dp[1], dp[2], ..., dp[5]까지의 값을 갱신합니다. 다음 숫자 2를 선택할 때는 dp[2], dp[3], ..., dp[5]까지를 갱신합니다.

3. dp[i] += dp[i - coin]; 부분:

이 부분이 핵심인데, 이전에 구해진 값을 바탕으로 현재 경우의 수를 갱신하는 역할을 합니다.

• dp[i]는 숫자 i를 만들 수 있는 경우의 수를 저장하는 값입니다.
• dp[i - coin]는 숫자 i에서 현재 선택한 coin(1, 2, 5)을 뺀 값을 만들 수 있는 경우의 수를 의미합니다. 즉, 숫자 coin을 추가해서 i를 만들 수 있는 경우의 수를 더해주는 역할을 합니다.

예시:

• 만약 i = 3이고 coin = 1일 때:
  • dp[3] += dp[3 - 1] = dp[3] += dp[2]
  • 즉, 숫자 2를 만드는 방법에 숫자 1을 추가하여 숫자 3을 만들 수 있는 경우의 수를 더해주는 것과 같습니다.
• 마찬가지로, i = 5이고 coin = 2일 때:
  • dp[5] += dp[5 - 2] = dp[5] += dp[3]
  • 즉, 숫자 3을 만드는 방법에 숫자 2를 추가하여 숫자 5를 만들 수 있는 경우의 수를 더해줍니다.

이 과정을 통해 점점 더 큰 숫자를 만들 수 있는 경우의 수를 계산하면서, 목표 숫자 target을 만드는 경우의 수를 구하게 됩니다.

동작 과정:

1. 숫자 1을 사용하여 dp[1]부터 dp[5]까지 업데이트합니다.
2. 그 다음 숫자 2를 사용하여 dp[2]부터 dp[5]까지 추가적으로 경우의 수를 더해줍니다.
3. 마지막으로 숫자 5를 사용하여 dp[5]까지의 경우의 수를 더합니다.

최종적으로 dp[target]에는 숫자 5를 만들 수 있는 모든 경우의 수가 저장됩니다.

 

import java.util.*;
class Solution {
    static final int MOD = 1_000_000_007;
    
    public int solution(int n, int[] money) {
        int answer = getCnt(n, money);
        return answer;
    }
    
    public int getCnt(int n, int[] money) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        for(int one : money) {
            for(int i=one; i<=n; i++) {
                dp[i] += dp[i-one];
            }
        }
        return dp[n];
    }
}