BOJ 2294 동전2(C++)

동전 2 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	7276	2245	1407	27.889%

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.)

입력

첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 100,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.

출력

첫째줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 

3 15
1
5
12

예제 출력 

3

힌트

출처

• 잘못된 조건을 찾은 사람: apples1309

알고리즘 분류

• 다이나믹 프로그래밍
• 동전 교환

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 28 29 30 31 32 33 34

#include    <cstdio> #include    <limits> #pragma warning (disable : 4996) #define min(x,y) (x) < (y) ? (x) : (y)   int C[111]; int M[111111]; int main() {     int n, k;     int coin;     scanf("%d%d", &n,&k);     for (int i = 1; i <= k; ++i)         M[i] = std::numeric_limits<int>::max()-1;           for (int i = 1; i <= n; ++i)     {         scanf("%d", &C[i]);         M[C[i]] = 1;     }     for (int i = 1; i <= k; ++i)     {         for (int j = 1; j <= n; ++j)         {             if (i - C[j] > 0)             {                 M[i] = min(M[i - C[j]] + 1, M[i]);             }         }     }     printf("%d", M[k] == std::numeric_limits<int>::max()-1 ? -1 : M[k]);       return 0; }

동전 1번과 거의 비슷한 문제. 

다이나믹 프로그래밍으로 풀었고 식 또한 거의 비슷했으나 이번엔 모든 경우의 수가 아닌 최소를 구하는 문제였다. 

때문에 비교하여 더 작은 값을 사용하였다.

이번 식은 D[i]를 i원을 만드는 최소 동전의 갯수로 할 때 

15를 만들 떄 1 5 12가 있다면 

D[15] = min(D[14], D[10], D[3]) + 1이다. 

14원을만드는 최소 동전의 수에 1원을 사용하거나

10원을 만드는 최소 동전의 수에 5원을 사용하거나

3원을 만드는 최소 동전의 수에 12원을 사용하는 것 중 가장 동전을 적게 사용하는 갯수가 15를 만드는 갯수가 되고

나머지도 이와 동일한 방법으로 구하면 된다.