동전 2
-
백준(BOJ) 2294번 동전 2알고리즘 풀이/백준(Boj) 2019. 8. 13. 16:27
문제 : https://www.acmicpc.net/problem/2294 문제n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 나의 풀이:반복적 동적 계획법을 통해 해결해보자 . cache[i] 는 i 원을 만들 수 있는 최소 동전의 수로 놓고 동적 계획법을 짜보자 예제 ) 코드 ( C++ ) #include #include using namespace std;int n, k;int coin[101];int cache[10001];const int INF = 987654321;int solve()..