[프로그래머스 3단계] 알고리즘 43. 거스름돈

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges) 2018년 5월 중순 프로그래머스 홈페이지가 업데이트가 되었습니다. 기존 알고리즘 단계 분류가 틀리니 참고하세요.

알고리즘 43. 거스름돈

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;

return answer;

}

}

풀이: 

이 문제는 전형적인 DP 문제이다. 먼저 간단한 기본 DP 부터 살펴보자. DP의 주된 아이디어는 다음과 같다. 

1. 2차원 배열을 만든다
2. 각 열은 총 금액이다.
3. 각 행은 총 금액을 낼 수 있는 경우의 수이다.
1. 만약 1, 2, 5라면 각 행의 경우의 수는 다음과 같다. 
1. 첫 행은 1원으로 낼 수 있는 경우의 수.
2. 둘째 행은 1, 2원으로 낼 수 있는 경우의 수
3. 셋째 행은 1, 2, 5원으로 낼 수 있는 경우의 수이다.

나의 코드는 다음과 같다.

class Solution {

public int solution(int n, int[] money) {

int answer = 0;

long[][] dp = new long[money.length][n+1];

for (int i=0; i<= n; i++){

dp[0][i] = (i % money[0] == 0) ? 1 : 0;

}

for (int i=1; i<money.length; i++){

for (int j=0; j<=n; j++){

dp[i][j] = dp[i-1][j];

for(int coin=1; coin <= j / money[i]; coin++){

dp[i][j] += dp[i-1][j-money[i] * coin];

}

}

}

answer = (int)(dp[money.length-1][n] % 1000000007);

return answer;

}

}

여기서 중요한 점은 이거다. 만약 j원에 대해서 1, 2, 5에서 낼 수 있는 경우의 수를 검사해보자. 이전에 1, 2를 검사한 행은 dp[i-1][j]일 것이다. 그것을 현재 dp[i][j]에 저장한다. 그 후 5원짜리가 1 개일때, 2개 일때 ... j / 5가 될때까지 검사를 한다. 테이블로 한번 나타내 보자.

	0	1	2	3	4	5
1	1	1	1	1	1	1
2 (1, 2로 표현)	1(1로 표현) + 0	1 + 0	1 + 1 = 2	1 + 1	1 + 2	1 + 2
5 (1, 2, 5)	1 + 0	1 + 0	2 + 0	2 + 0	2 + 0	3 + 1

n=5일 때 1를 검사할 때 경우의 수를 살펴보자.

1 5개 1 1 1 1 1     = dp[0][5] = 1

총 1가지이다.

n=5일 때 1, 2를 검사할 때 경우의 수를 살펴보자.

2원 0개 1 1 1 1 1  = dp [1][5] = dp[0][5 - (2*0)]                    

---------------------------- 여기까지가 1로 검사했던 경우의 수이다.

2원 1개1 1 1 2      = dp[1][5] += dp[0][5-(2*1)]                        

2원 2개 1 2 2        = dp[1][5] += dp[0][5-(2*2)]                   

그래서 총 3가지이다.

이번엔 1, 2, 5로 검사해보자.

5원 0개일 때        = dp[2][5] = dp[1][5-(5*0)]

1 1 1 1 1              

1 1 1 2            

1 2 2

------------------------(여기까지가 1, 2로 검사했던 경우의 수다.)

5원 1개               = dp[2][5] = dp[1][5-(5*1)]

5   

그래서 총 4가지이다. 

나의 DP 아이디어를 이해했는가? money[i]에 대해 검사하고 있을 때 그 동전이 0개일 때는 이전의 검사했던 경우의 수이다. 1개씩 늘어날때마다 이전 결과에서 [j-(money[i] * 동전수)] 인덱스의 경우의 수를 나타낸다. 

그러나 문제점!

그런데 이 코드를 실행하면 효율성 검사에서 시간초과가 나온다. (필자 같은 경우 이 문제를 1주일동안 고민했었다.) 그러던 중 dp를 효율적으로 계산할 방법이 떠올랐다. 기본적으로 위의 아이디어는 최악의 시간복잡도가 n의 3제곱이다. 내가 개선할 아이디어는 n의 제곱으로 문제를 풀 수 있다. 일단 테이블을 살펴보자. 예를 일반화해서 보기 위해 입력값을 좀 크게 해보았다. n=11 money = {2, 3, 5, 7}이다. 그러면 테이블은 다음과 같다.

	0	1	2	3	4	5	6	7	8	9	10	11
2	1	0	1	0	1	0	1	0	1	0	1	0
3	1	0	1	1	1	1	2	1	2	2	2	2
5	1	0	1	1	1	2	2	2	2	3	4	4
7	1	0	1	1	1	2	2	3	2	4	5	5

우선 첫 행은 기존 아이디어와 같다. 이제부터 주의깊게 살펴보자. 먼저 3일 때이다.

	0	1	2	3	4	5	6	7	8	9	10	11
2	1	0	1	0	1	0	1	0	1	0	1	0
3	1	0	1	1	1	1	2	1	2	2	2	2
5	1	0	1	1	1	2	2	2	2	3	4	4
7	1	0	1	1	1	2	2	3	2	4	5	5

이 색칠한 테이블의 공통점이 무엇인지 아는가? 나의 아이디어의 힌트이다!  정답은 바로 이것이다.

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

그럼 5를 한번 살펴보자.

	0	1	2	3	4	5	6	7	8	9	10	11
2	1	0	1	0	1	0	1	0	1	0	1	0
3	1	0	1	1	1	1	2	1	2	2	2	2
5	1	0	1	1	1	2	2	2	2	3	4	4
7	1	0	1	1	1	2	2	3	2	4	5	5

5 역시 다음과 같은 규칙을 따른다.

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

이번엔 7을 살펴보자.

	0	1	2	3	4	5	6	7	8	9	10	11
2	1	0	1	0	1	0	1	0	1	0	1	0
3	1	0	1	1	1	1	2	1	2	2	2	2
5	1	0	1	1	1	2	2	2	2	3	4	4
7	1	0	1	1	1	2	2	3	2	4	5	5

7 역시 이런 규칙을 따른다.

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

그렇다면 점화식을 다음과 같이 쓸 수 있다.

j >= money[i]

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

else

dp[i][j] = dp[i-1][j];

나의 총 코드는 다음과 같다.

class Solution {

public int solution(int n, int[] money) {

int answer = 0;

long [] dp = new long[n+1];

for(int i=0; i<=n; i++){

dp[i] = (i % money[0] == 0) ? 1 : 0;

}

for(int i=1; i<money.length; i++){

for(int j=money[i]; j<=n; j++){

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

}

}

answer = (int)(dp[n] % 1000000007);

return answer;

}

}

약간의 설명을 덧붙이자면 나는 1차원 배열로 풀었다. 왜냐하면 어차피 j >= money[i] 일때만 값이 추가되기 때문에 그 이전에는 검사할 필요가 없다고 판단해서이다. 진짜 이번 문제는 기특하게 풀었다.