[백준 BOJ][DP] 2293 동전 1

2293_동전 1

 

링크

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

 

풀이

 

 

일단 k원을 만들 수 있는 경우의 수를 담을 배열 DP[10001]과 가치를 가진 동전을 담을 배열 coin[101]을 만들어 줍니다.

 

그리고 DP[0]은 동전을 가지고 0원을 만들 경우의 수이니 1로 초기화 해줍니다.

 

예제로 설명을 하자면, 1원, 2원, 5원짜리 동전으로 10원을 만드는 경우의 수를 구해야 합니다.

 

DP[n] = DP[n-1] + DP[n-2] + DP[n-5]

1원을 만들려면 0원에 + 1원을 해줍니다. 1가지

2원을 만들려면 0원에 + 2원을 해주거나 1원에 + 1원을 해줍니다. 2가지

3원을 만들려면 1원에 + 2원을 해주거나 2원에 + 1원을 해줍니다. 3가지 (2가지인데 중복이 생김)

 

그러니 저 점화식에 1~n까지 넣는 방식을 사용하면 안 됩니다.

 

 

i는 1부터 n까지, j는 coin[i]부터 k까지 for문을 돌립니다.

 

DP[j] += DP[j – coin[i]] -> j - coin[i]에서 coin[i]을 더해 만드는 경우의 수

이렇게 식을 짜서 돌리면 중복을 제거하고 경우의 수를 구할 수 있습니다.

 

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

//2293_동전 1 #include <iostream> using namespace std;   int DP[10001] = { 1 }, coin[101];   int main() {     int n, k;     int i, j;       cin >> n >> k;       for (i = 1; i <= n; ++i) {         cin >> coin[i];           for (j = coin[i]; j <= k; ++j) {             DP[j] += DP[j - coin[i]];         }     }       cout << DP[k] << endl;       return 0; } Colored by Color Scripter

cs