[프로그래머스 level 3][JAVA] 12907번: 거스름돈

[level 3] 거스름돈 - 12907

문제 링크

성능 요약

메모리: 94.8 MB, 시간: 61.18 ms

문제 설명

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
문제의 예시와 같습니다.

 

풀이과정

예시1

 

빨간색으로 색칠된 부분은 자기 자신, money(2)에서는 n이 2일 때 2인 자기 자신의 경우의 수로 추가된다.

dp[i][j] = dp[i-1][j] + dp[i][j-money[i-1]

두번째 줄을 보면 2(1,2)이 1,2를 조합해서 경우의 수를 만드는데 1 = 1 / 2 = 1+1, 2 / 3=1+1+1, 2+1라는 경우의 수가 있다.

여기서 규칙을 찾아 낼 수 있다. money(2)에서 n을 표현하려면 table[1][2]는 table[0][2]를 표현하는 경우의 수와 table[1][2-2]를 표현하는 경우의 수를 더한 것이라는 거다.

 

i=1부터 시작한다. i=0 행은 “동전을 하나도 사용하지 않은 경우”를 의미하는 초기값으로 사용한다.

dp 행 번호(i) 실제 의미 사용 가능한 동전

0	동전 없음	[]
1	money[0]만 사용	[1]
2	money[0], money[1] 사용	[1,2]
3	money[0], money[1], money[2] 사용	[1,2,5]

 

예시2

다른 수의 배열을 살펴보자

한 가지 규칙을 더 발견할 수 있다. dp[i][j] = dp[i-1][j];

자기 자신이 나타나기 전의 경우의 수는 위에서 표현한 경우와 수와 같다.  

money(7)에서 10을 표현한 경우의 수와 8에서 10-8, money(8)에서 2를 표현한 경우의 수를 더해주는 것이다.

2를 표현한 경우의 수에서 8을 더하면 10이 되니까 어떻게든 2를 표현했다면 8을 더해주기만 하면 10이 되기 때문이다.

dp[i][10] = dp[i-1][10] + dp[i][10 - 8]  = dp[i-1][10] + dp[i][2]

 

자바 코드

class Solution {
    int[][] dp;
    
    public int solution(int n, int[] money) {
        dp = new int[money.length+1][n+1];
        int answer = 0;
        
        for(int i = 1; i < money.length+1; i++) {
            for(int j = 0; j < n+1; j++) {
                if(j == 0)
                    dp[i][j] = 1;
                else {
                    if(j < money[i-1])
                        dp[i][j] = dp[i-1][j];
                    else
                        dp[i][j] = (dp[i-1][j] + dp[i][j-money[i-1]]) % 1000000007;
                }
            }
        }
        return dp[money.length][n];
    }
}

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

참고:https://tosuccess.tistory.com/57