https://www.acmicpc.net/problem/2294
2294번: 동전 2
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어
www.acmicpc.net
시간이 c++치고 엄청 오래걸린다. 배열을 안쓰고 벡터로 풀어서 그런건가??
동전 문제는 그리디 알고리즘으로 최적해를 구할 수 있는 경우가 있고 없는 경우가 있다고 배웠는데,
까먹어서 Chat GPT한테 물어봤다.
동전 거스름돈 문제에서 동전의 단위가 서로 배수 관계가 아닐 경우 그리디 알고리즘은 최적해를 보장하지 못한다.
*최적 부분 구조(optimal substructure)와 **탐욕적 선택 속성(greedy choice property)이 성립하지 않기 때문이다.
반면 동전의 단위가 서로 배수인 경우, 가장 큰 단위의 동전부터 최대한 많이 사용하는 것이 최적의 해를 보장하는 이유는, 작은 단위의 동전을 사용하면 더 많은 동전이 필요하게 되기 때문이다.
*최적 부분 구조: 각각의 부분 문제의 최적해가 있으면 전체 문제의 최적해를 얻어낼 수 있는 경우
**탐욕적 선택 속성: 각각의 단계에서의 탐욕적인 선택이 최종 답을 구하기 위한 최적의 선택인 경우
아무튼 이 문제는 dp로 풀어야 한다.
점화식은 다음과 같이 세웠다.
dp[k]는 k원을 만들 수 있는 동전의 최소 개수이다.
dp[k] = min(dp[k - 1] + dp[1], dp[k - 2] + dp[2], ... , dp[k / 2] + dp[n / 2])
(단, dp[k - 1], dp[k - 2], ... , dp[1] 중 불가능한 (값이 -1인) 경우에는 비교하지 않는다.)
dp[x] = 1 (x는 coins 의 원소)
참고
Chat GPT🤖
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준] 1932번: 정수 삼각형 (0) | 2023.10.13 |
|---|---|
| [백준] 2293번: 동전 1 (0) | 2023.10.06 |
| [백준] 1520번: 내리막 길 (0) | 2023.10.04 |
| [백준] 1890번: 점프 (0) | 2023.10.03 |
| [백준] 11048번: 이동하기 (0) | 2023.10.02 |