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

문제주소 :programmers.co.kr/learn/courses/30/lessons/12907?language=java

코딩테스트 연습 - 거스름돈

---

<문제 설명>

문제 설명

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

 

<풀이법>

▒ 한줄 개념: 동적 계획법 ▒ 

두번 정도 이전에 시도했었다가 실패했던 문제로, dp 문제를 푸는 요령을 다시 한번 익히게 해준 문제이다. 

dp의 핵심은 과거에 저장해둔 값을 바탕으로 현재 값을 도출해내는 것이다. 어떤 규칙에 대한 점화식을 통해서, 필요한 값을 얻어내는 과정이 중요한 알고리즘인 것이다. 

따라서 dp 문제에서 중요한 것은 어떤 값을 어떻게 저장할 것인가? 가 가장 핵심이 된다. 이를 알기 위해선, 다음과 같은 방식으로 풀이를 진행해야한다.

 

1. 일정량의 데이터를 직접 손으로 작성해보기

2. 이전값들을 이용해서 현재 값을 구할 수 있는 방식을 찾아내기

3. 찾아낸 방식을 점화석으로써 코드에 적용하기

 

dp문제의 대부분은 막상 점화식으로 코드를 작성해보면 보통 짧고 단순하기 때문에, 1~2번 과정이 가장 중요하게 된다.

 

 

문제의 예제를 가져와보면 다음과 같다.

이 예제에 대해, 1~8까지 나올 수 있는 경우는 다음과 같다.

이 표를 가지고 어떻게 쪼개서 dp를 짜야할까 고민을 해보아야 했다. 다양한 방식으로 계속 이것저것 조합해보았는데, 결국 찾아낸 방식은 다음과 같았다.

1만 쓴 조합, 2가 추가된 조합, 5가 추가된 조합으로 구분을 지어놓았다.

이를 dp에 항상 사용되는 2차원 배열을 통해 다시 작성해보면, 다음과 같다.

이 표에서, 위의 색깔들을 표현해보면 다음과 같다. 즉, 1로만 이루어진 경우, [1,2]로 이루어진 경우, [1,2,5]로 이루어진 경우를 나눠보는 것이다.

 

각 경우를 나눈 것

여기서 보면, 2원이 추가 되었을 때, 2원보다 큰 값에서만 2가 포함된다. 5원이 추가되었을 때에도, 5원보다 큰 값에서만 5가 포함된다.

이를 바탕으로, 규칙을 찾아내면 다음과 같다.

dp[i][j] = dp[i-1][j] + dp[i][j - money[i]] 라는 점화식이 나오게 되는 것이다.

 

 

만약 1,2,3,4원 같이 -5원을 하였을 때 음수가 나오는 칸이라면, dp[i-1][j]를 그대로 가져오면 된다.

 

 

<코드(Python)>

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];
        }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest