[백준 2293번] 동전 1 (C++)

문제링크 : https://www.acmicpc.net/problem/2293

2293번: 동전 1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[101];
int dp[10001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N, K;
    cin >> N >> K;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    dp[0]=1; //초기값

    for(int i=0; i<N; i++) //동전 갯수
    {
        for(int j=arr[i]; j<=K; j++) //합
        {
            dp[j] = dp[j] + dp[j-arr[i]];
        }
    }

    cout << dp[K];

    return 0;
}

배낭 문제와 유사한 DP 문제이다.

현재 동전의 가치를 기준으로 합을 이루는 경우의 수를 저장해준다.

 

<arr[1]>
dp[1] = dp[1] + dp[1-1] -> 1 (dp[0]=1)
dp[2] = dp[2] + dp[2-1] -> 1
dp[3] = dp[3] + dp[3-1] -> 1
dp[4] = dp[4] + dp[4-1] -> 1
.
.
.
dp[10] = dp[10] + dp[10-1] -> 1
-> 각 수를 1로 표현하는 경우

<arr[2]>
dp[2] = dp[2] + dp[2-2] -> 2
dp[3] = dp[3] + dp[3-2] -> 2
dp[4] = dp[4] + dp[4-2] -> 3
dp[5] = dp[5] + dp[5-2] -> 3
dp[6] = dp[6] + dp[6-2] -> 4
dp[7] = dp[7] + dp[7-2] -> 4
dp[8] = dp[8] + dp[8-2] -> 5
dp[9] = dp[9] + dp[9-2] -> 5
dp[10] = dp[10] + dp[10-2] -> 6
-> 1로 표현한 경우 + 2로도 표현한 경우

<arr[3]>
dp[5] = dp[5] + dp[5-5] -> 4
dp[6] = dp[6] + dp[6-5] -> 5
dp[7] = dp[7] + dp[7-5] -> 6
dp[8] = dp[8] + dp[8-5] -> 7
dp[9] = dp[9] + dp[9-5] -> 8
dp[10] = dp[10] + dp[10-5] -> 10
-> 1로 표현한 경우 + 2로도 표현한 경우 + 5로도 표현한 경우