4 ★★★ 프로그래머스 - 거스름돈 (DP)
220605
어렵ㅠ
220317
dp[i]를 dp[m]으로 바꾸는게 훨씬 보기 편할 수도.. 차라리 dp[money] 풀네임 쓰거나 i, j로 쓰면 헷갈릴 수가 있음
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import java.util.*;
class Solution {
public int solution(int n, int[] moneys) {
Arrays.sort(moneys);
int[] dp = new int[n+1];
dp[0] = 1;
for(int money=1; money<=n; money++){
dp[money] = (money%moneys[0]==0)? 1:0;
}
for(int j=1; j<moneys.length; j++){
for(int money=moneys[j]; money<=n; money++){
dp[money] = (dp[money] + dp[money-moneys[j]])%1000000007;
}
}
return dp[n];
}
}
|
cs |
220312
또 푸는데 더럽게 어려웠다..
이건 dp에 도를 터고 있어야 풀리는 문제인듯
코드는 진짜 짧은데 저 점화식이 왜 저렇게 탄생됐는지
그리고 매우 의아했던 dp[0]=1인지..
당연히 0원을 만들 수 있는 경우의 수는 없는데 왜 1을 넣어야 코드가 돌아가는지..
결론만 말하면 dp[0]=1은 점화식을 충족시키기 위해 값을 끌어오는거임 dp[1]~dp[n]까지는 1원부터 n원까지 만들 수 있는 경우의 수가 맞는데 dp[0] 혼자 아니라는 얘기임 1차원1배열로 만들기 위해 끌어다 쓴거임
점화식 탄생은 2번째링크보고 본문보니까 이해됨..
dp[0]=1인 이유, dp를 2차원배열에서 1차원배열로
만들 수 있는 이유(이건 누적을 이용해서 차원하나를 지워버린거임)..
걍 점화식만 띡 보고 이해 절대 불가능함(내 수준 기준으로)
혼자서 끙끙 앓다가 해설 보고 풀었음.
문제에서 점화식을 정의할 수 있는 테이블을 만들어야하는데
나같은 경우는 쓸데없이 1부터 n까지의 금액을 만들 수 있는 동전조합의 경우를 전부 써서 만들어봤는데
그런 식으로 해서는 절대로 규칙을 못찾고 ,
일정한 규칙을 이루는 table을 찾아야하는데 (점화식을 찾기 위해서)
행은 동전의 단위 개수(오름차순 순으로 1개,2개,3개 이렇게)
열은 1부터 n까지의 금액 total값으로 해줘야 규칙을 찾을 수 있음.
/*
ex)문제에서 주어진 예시의 돈의 종류인 1,2,5와 거슬러 주어야하는 금액이 5일 때,
// i는 동전 단위의 조합 수. j는 거슬러주어야하는 금액
즉
i=0 --> 1원 1개만 사용 가능한 경우
i=1 --> 1,2원 2개 사용 가능한 경우
i=2 --> 1,2,5원 3개 사용 가능한 경우
dp[1][5] -> 1,2원 2종류의 동전들을 사용하여 5원을 거슬러줄 수 있는 경우의 수
dp[0][10] -> 1원 1종류의 동전들을 사용하여 10원을 거슬러줄 수 있는 경우의 수
dp[2][30] -> 1,2,5원 3종류의 동전들을 사용하여 30원을 거슬러줄 수 있는 경우의 수
이렇게 구분하는 이유는 새로운 돈의 단위값이 튀어나오기 전까지는
즉 2원만 쓰는 경우와 2,3원 두개를 쓰는 경우를 비교해볼 때
3원을 거슬러주기전까지 경우의수는 서로 같다는 것이다.
아
밑에 참조된 블로그 2개 글 정독 5번은 해서 이해한 것 같다.
int[][] dp = new int[money.length][n+1];
dp[i][j] = dp[i-1][j] + dp[i][j- (현재money단위)];*/
설명은 밑에 참조된 블로그 글 2개 ㄱ 글자로 쓰려니까 도저히 못하겟다
솔직히 해설 안보면 하루종일 풀어도 절대 못풀었을듯..
특정한 dp[i][j] 값을 만들기 위해 2가지 경우에서 끌어와야함
하나는 dp[i-1][j] 다른 하나는 dp[i][j-(현재 새로운money의 단위)]
근데 이거 dp를 또 2차원 배열로 풀면 메모리가 부족해서 효율성에서 틀린다.
즉 dp[i][j]를 만들기위해 끌어야하는 값들 중 하나인 dp[i-1][j]를
1차원 배열인 dp[j]로 표현해주려면 기존에 저장된 dp[j]값을 그대로 활용해주면됨(이것도 이해하느라 몇십분걸림)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public int solution(int n, int[] money) {
int answer = 0;
int[] dp = new int[n+1];
dp[0]=1;
for(int j=0; j<=n; j++){
if( j%money[0]==0 ) dp[j]=1;
}
// for(long i : dp){
// System.out.print(i+" ");
// }
// System.out.println();
for(int i=1; i<money.length; i++){
for(int j=money[i]; j<=n; j++){
dp[j] = (dp[j] + dp[ j-money[i] ])%1000000007;
// System.out.println(dp[j]);
}
// for(long k : dp){
// System.out.print(k+" ");
// }
// System.out.println();
}
return dp[n];
}
|
cs |
참조 링크