[프로그래머스 Level.3] 거스름돈 (연습문제) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 연습문제 > 거스름돈

 

 

 

문제 설명

 

 

Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.

 

예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다.

 

• 1원을 5개 사용해서 거슬러 준다.
• 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다.
• 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다.
• 5원을 1개 사용해서 거슬러 준다.

 

거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세요.

 

 

 

제한 사항

• n은 100,000 이하의 자연수입니다.
• 화폐 단위는 100종류 이하입니다.
• 모든 화폐는 무한하게 있다고 가정합니다.
• 정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지를 return 해주세요.

 

---

 

입출력 예

n	money	result
5	[1,2,5]	4

 

 

입출력 예 설명

 

입출력 예 #1

문제의 예시와 같습니다.

 

 

 

 

 

 

나의 코드

class Solution {
    public int solution(int n, int[] money) {
        int answer = 0;
        
        int[] dp = new int[n+1];
        dp[0] = 1; 
        
        // 화폐의 단위를 돌면서 각 거슬러줘야 할 금액일 때 거슬러줄 수 있는 방법을 계속 더해준다.
        for(int i=0; i<money.length; i++) {
            for(int j=money[i]; j<=n; j++) {
                dp[j] += dp[j - money[i]] % 1000000007; // dp[현재 거슬러줘야 할 가격] += dp[현재 거슬러줘야 할 가격 - 현재 화폐 단위]
            }
        }
        
        answer = dp[n];
        
        return answer;
    }
}

 

풀이

1. dp로 푸는 문제로 생각하기 어려운 문제였다.
2. int형 배열 dp를 만들고 각 거슬러줘야 할 금액일 때 거슬러줄 수 있는 방법을 계속해서 더해주어 구한다.
3. 각 화폐단위일 때마다 dp[n]까지 for문을 돌면서 해당 화폐단위로 거슬러줄 수 있는 방법을 계속해서 더해준다.
4. 기본적으로 money[i]가 1이라면 1원으로 해당 금액만큼 거슬러주는 방법이므로 각 dp에 1씩 더해줄 것이다.
5. 이제 나머지 money[i]의 방법을 더해주면 되는데 만약 이번에 money[i]가 2원이고 dp[3]으로 3원을 거슬러줄 때의 방법을 구한다면 현재 화폐단위인 2원일 때 우선 2원으로 거슬러주면 나머지 1원을 거슬러주면 되기 때문에 2원으로 거슬러 준 다음인 나머지 1원을 거슬러줄 수 있는 방법인 dp[1]을 더해주면 되는 것이다.
6. 마찬가지로 money[i]가 2원이고 dp[4]라면 4원을 거슬러줄 때의 방법은 화폐단위인 2원으로 한 번 주고나면 나머지 2원을 거슬러줄 수 있는 방법을 더해주면 된다. 따라서 2원을 거슬러주는 방법의 수인 dp[2]를 더해주면 된다.
7. 그래서 점화식을 구해보면 dp[현재 거슬러줘야 할 가격] += dp[현재 거슬러줘야 할 가격 - 현재 화폐 단위] 가 된다.
8. 여기서 dp[2]일 때 money[i]가 2라면 dp[2] += dp[2-2]가 되는데 이것 또한 2원으로 전부 거슬러주는 한 가지 방법이기 떄문에 dp[0]을 1으로 세팅하는 것이다.
9.  그리고  dp[4] 일 때 money[i]가 5이면 5원으로는 4원을 거슬러줄 수 없기(dp[4-5]) 때문에 j를 money[i] 크기부터 시작하는 것이다.
10. 이렇게 각 화폐단위일 때 해당 화폐단위 크기부터 n까지 dp를 for문을 돌아 각 거슬러 줄 수 있는 방법을 누적해서(수가 커질 수 있으므로 더할 때마다 % 1000000007로 나누어 더해준다) 구한 뒤에 최종적으로 n원을 거슬러줄 수 있는 방법인 dp[n]을 answer에 저장하고 반환하면 된다.

 

 

참고 : https://school.programmers.co.kr/questions/25161