Today I learned
오늘은 토요일 코테 대비 프로그래머스에서 랜덤한 코테 문제를 풀어봤다. 정석적이고 기초적인 DP 문제라 풀긴했지만 아직 DP 쪽이 약한지 시간이 좀 걸렸다. DP 쪽 문제를 더 풀어봐야겠다.
거스름돈
https://school.programmers.co.kr/learn/courses/30/lessons/12907
문제
100,000 이하의 자연수 n 이 주어지고, 각 화폐 가격이 담긴 int 배열 money가 주어진다. 거슬러 줘야 하는 돈 n 을 money에 있는 화폐로 거슬러줄 수 있는 경우의 수를 1,000,000,007로 나눠서 반환해라.
풀이 과정
- 문제를 딱 보자마자 dp로 풀면 된다고 생각했다. 일단 거스름돈 자체가 DP의 가장 유명한 예시기도 하고, 문제 자체도 경우의수가 너무 많아져 소수로 나눠 반환하라고 하니 일반적으로 계산하면 효율성에서 out 될 가능성이 커보였다. 그래서 DP를 활용하는 것이 좋아보였다.
- 우선 DP로 풀기 위해 규칙을 찾아야 했다. 주어진 예시 1,2,5 화폐로 5원을 거슬러 주는 경우의 수를 종이에 적어가며 풀어봤다.
| money\n | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1,2 | 1 | 1 | 2 | 2 | 3 | 3 |
| 1,2,5 | 1 | 1 | 2 | 2 | 3 | 4 |
-
위의 표에서 행은 money, 즉 화폐의 경우의 수이고, 열은 n 구해야하는 수다.
안의 값들은 낼 수 있는 경우의 수이다.
우선 n=0 이면 아무것도 안내면 되니 모든 경우의 수가 1이다.
1원만 있을때는 모든 돈을 1원으로 내면 되니 1로만 채워진다.
화폐가 1,2 2개가 되면 2부터 시작해서 2의 배수가 1씩 증가한다.
3개가 되면 5에서 1개의 경우의 수가 추가되었다. -
위를 규칙으로 나타내면,
현재칸 = 바로 위칸 + 이번에 추가된 화폐금액만큼 왼쪽 칸 이라 할 수 있다.
점화식으로 나타내면 아래와 같다.
dp[i][j] = dp[i-1][j] + dp[i][j-money[i]] -
우선 money를 오름차순으로 정렬해두고, 2차원 dp배열을 화폐수, n 이 마지막 자리에 오도록 크기를 설정해 만든다.
이중for문을 만들어 밖의 for문은 1~len까지, 안의 for문은 0~n까지 만든다. -
j=0 즉, 0원을 내야되는 경우의 수는 모든 경우 1이니 그 조건을 넣는다.
-
만약 새로 추가된 화폐가치보다 x좌표가 작다면 바로 위 값만 더한다.
(dp배열이 0부터 시작하니 값을 맞추기위해 i대신 i-1을 쓴다.) -
아니라면 위에서 구한 점화식을 적용하되, 문제에서 주어진 소수를 이용해 나눠서 저장한다.
-
마지막값인 dp[len][n]을 반환하면 끝.
DP 문제 팁
-
DP는 직접 손으로 어느정도 써보고 규칙을 찾는 것이 오히려 더 쉬운 것 같다.
-
문제에서 구해야 되는 답을 중심으로 배열 or 이차원 배열을 사용해 값을 저장하는 자료구조를 만들고 규칙을 찾아 만든 점화식을 여기에 대입하면 좋다.
-
2차원배열은 dp[y][x]. 즉, y가 먼저, x가 뒤이기 때문에 조심해야 한다.
Java 코드
import java.util.*;
class Solution {
public int solution(int n, int[] money) {
int len = money.length;
int[][] dp = new int[len+1][n+1];
Arrays.sort(money);
for(int i=1; i<=len; i++){
for(int j=0; j<=n; 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[len][n];
}
}