[c++][백준2293][백준 동전1][dp]

문제

풀이 방법

겹치면 안된다. 따라서 다음과 같이 풀었다.(예제 입력인 3-10, 1,2,5로 설명)

1.전부 1로 채우는 경우

2.전부 1로 채우는 경우에 무조건 '2'가 한개 이상 들어가는 경우

3.전부 1,2로 채우는 경우에 무조건 '3'이 한개 이상 들어가는 경우

3까지 가면 완료이다!

코드

#include <iostream>
using namespace std;
int main()
{
    unsigned int dp[10001] = {0,};
    int arr[100] = { 0, };
    int n, k,x=0,y=1,r=0;
    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 - arr[i]];
        }
    }
cout << dp[k]<<endl;
    return 0;
}