https://www.acmicpc.net/problem/2293
2293번: 동전 1
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
www.acmicpc.net
처음에는 이렇게 점화식을 세웠는데
dp[i] += dp[i - coins[j]]
중복이 아주 많이 나오기 때문에 계속 고민했다.
아무리 생각해봐도 점화식을 못세우겠어서 결국 풀이를 찾아봤다.
풀이를 이해한 바로는,
동전이 0원짜리 1개 있는 경우
동전이 0원짜리, 1원짜리 2개 있는 경우
...
이렇게 동전의 개수를 늘려가면서 dp배열을 갱신해야 하는 것 같다.
i == 6일 때 예를 들어보면
0원 1개 있는 경우
=> dp[6] = 0
1원 추가된 경우
1 1 1 1 1 1
=> dp[6] = 1
2원 추가된 경우
1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2
=> dp[6] = dp[6] + dp[4]
5원 추가된 경우
1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2
1 5
=> dp[6] = dp[6] + dp[1]
참고
2293번 풀이: https://danidani-de.tistory.com/5
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준] 14002번: 가장 긴 증가하는 부분 수열 4 (0) | 2023.11.10 |
|---|---|
| [백준] 1932번: 정수 삼각형 (0) | 2023.10.13 |
| [백준] 2294번: 동전 2 (0) | 2023.10.05 |
| [백준] 1520번: 내리막 길 (0) | 2023.10.04 |
| [백준] 1890번: 점프 (0) | 2023.10.03 |