백준 2293번 - 동전 1

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

이전에 풀었던 붕어빵 판매하기와 유사한 문제이다.
차이점은 최대 수익이 아닌 해당 가치에 대한 경우의 수를 구하는 문제이다.


저장하려는 변수 값을 dp라고 가정한다면
dp[0]에 1을 저장한 다음에 첫 번째 종류의 동전의 가치만큼 계속해서 저장해주면 된다.

만약 그 가치가 2였다면
dp[0+2]=dp[0+2]+dp[0]
dp[1+2]=dp[1+2]+dp[1]
...
와 같이 진행된다. 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    
    int n,k;
    cin>>n>>k;
    
    int arr[101];
    int dp[10001]={0};
    
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    
 
    dp[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j+arr[i]<=k;j++)
            if(dp[j])
                dp[j+arr[i]]+=dp[j];
    
    
    cout<<dp[k]<<endl;
    return 0;
}