180131_2293_동전1

//https://www.acmicpc.net/problem/2293 #include <iostream>

using namespace std;

int dp[10001];

int value[101];

int main()

{

int n, k;

cin >> n >> k;

for(int i=0; i<n; i++) cin >> value[i];

dp[0]=1;

for(int i=0; i<n; i++){

for(int j=1; j<=k; j++){

if(j>=value[i]){

dp[j]+=dp[j-value[i]];

}

}

}

cout << dp[k];

}

다시 풀어보기, 점화식은 제대로 세웠는데 접근을 잘못했음

dp[i]= dp[i-value[0]]+ dp[i-value[1]]+ ... +dp[i-value[n-1]]

이여야함.

 또, i>=value[j]여야함.

왜냐면, value[j]가 하나의 묶음. 즉, dp[i-value[j]]일때에 value[j]만큼의 단위가 더해진 값, 이런 경우를 모두 합해주는 것.

백준 예시인

3, 10

1,2,5

의 경우 

dp[i]=dp[i-1]+dp[i-2]+dp[i-5]

i가 4인 경우

dp[4]= dp[3]( 3에 가치가 1인 동전 한개를 더한 것과 같음 경우의 수는 같음)

+dp[2] ( 2에 가치가 2인 동전 한개를 더한 것과 같음 경우의 수는 같음)

//+dp[4-5] ::  4>=5이므로 계산에 포함 x