백준 2293번. 동전 1(c++) / DP

이 문제는 실제 N* 게임회사에서 나왔던 코딩테스트 문제와 거의 99%일치하는 문제였는데....

아쉽게도 시험에서는 풀지 못해서 백준에서 유사한 문제를 기여코 찾아내서 풀었다...ㅎㅎ

 

처음에 봤을 때는, 중학교때 풀었던 경우의 수? 같은 문제여서 대충 DP로 푸는 문제구나 싶었긴 했는데....

결국은 아래 블로그의 풀이를 참고해서 풀었다..;; (DP는 왜 이렇게 어려울까?ㅎㅎ)

blog.naver.com/occidere/220784778900

 

#include <iostream>
#include <vector>
using namespace std;
 
int n, k;
int dp[10001] = {0, };
vector<int> v;
 
int main()
{
    cin>>n>>k;
    v.resize(n);
    for(int i=0; i<n; i++){
        cin>>v[i];
    }
 
    dp[0] = 1;
 
    for(int i=0; i<v.size(); i++){ // 각각의 v[i](가중치)를 가지고 j값을 만드는 것..
        for(int j=v[i]; j<=k; j++){
            dp[j] += dp[j-v[i]];
        }
    }
 
    cout<<dp[k]<<"\n";
    return 0;
}