[2293번] 동전 1

문제 출처 :

https://www.acmicpc.net/problem/2293

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

해결책이 보이면 아주 간단하고, 잘못 접근하면 조금 까다로운 문제인 것 같다.

나는 두번의 DP 점화식을 거친 후 AC를 받았다.

첫번째 DP 점화식은 

for (int i = 1; i <= m; i++)
    for (int j = 0; j < n; j++)
        if(i - coin[j] >= 0)
            DP[i] += DP[i - coin[j]];
 

다음과 같이 짰는데, 이 DP는 수행 과정에서 결함이 생긴다.

만약 3원을 만들고 싶다면 1원 + 1원 + 1원 혹은 1원 + 2원으로 하면 3원이 되는데 

이 코드는 1원 + 1원 + 1원, 1원 + 2원, 2원 + 1원 총 3개의 답을 도출해주기 때문이다.

따라서 아래와 같이 수정을 함으로써 문제를 해결하였다.

for (int i = 0; i < n; i++)
    for (int j = 1; j <= m; j++)
        if (j - coin[i] >= 0)
            DP[j] += DP[j - coin[i]];

이렇게 바꾼 DP 점화식 의미는, 만약 1,2,5원이 있다면

동전 1원으로 만들 수 있는 모든 값을 다 구해주고,(DP[1]~DP[N]까지 모두 1이 되게 된다.)

동전 2원으로 만들 수 있는 모든 값을 다 구해주고,

동전 5원으로 만들 수 있는 모든 값을 다 구해준다.

첫번째 코드는 이번 DP값을 존재하는 COIN들로 더할 수 있으면 DP를 갱신하는 것이고

두번째 코드는 이번 COIN으로 DP값을 갱신 할 수 있다면 DP를 갱신하는 것으로 조금 다르다.

소스 코드 : 

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 35 36 37 38

#include <iostream> #include <cstdio> #include <map>   using namespace std;   int coin[10002]; int DP[10002];   int main() {     int n, m;     scanf("%d %d", &n, &m);       for (int i = 0; i < n; i++)         scanf("%d", &coin[i]);          DP[0] = 1;       for (int i = 0; i < n; i++)         for (int j = 1; j <= m; j++)             if (j - coin[i] >= 0)                 DP[j] += DP[j - coin[i]];       /*     for (int i = 1; i <= m; i++)         for (int j = 0; j < n; j++)             if(i - coin[j] >= 0)                 DP[i] += DP[i - coin[j]];     */          cout << DP[m];       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus