백준, BOJ, 2293번 C++ [CPP] *

용량도 작다

 

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

 

---

심히 기분이 좋지 않다.

 

재귀로 푸는 방법을 알았지만.. 용량도.. 시간도 초과할 것이 뻔했다.

 

다른 방법을 찾는데.. 너무 헤맸다.

이러한 방법은 정말 많은데

충분히 익혀놔야할 방법 중 하나같다.

 

하향식보다 이번엔 상향식으로 하는 것이 맞았다.dp에 저장해가며 푸는 것이 이 문제의 핵심이었을 것이다.

 

#include <iostream>

using namespace std;

int n,k;

int coin[101];

int dp[100001];

int main(){
    cin >> n >> k;
    
    for(int i = 1; i<=n; i++){
        int a;
        cin >> a;
        coin[i] = a;
    }
    
    //dp[0] = 1 을 추가시켜주어야함
    //첫번째 코인으로 만들 수 있는 경우의 수를 추가
    //첫번째 코인으로 만들 수 있는 값에서 다음 코인의 값을 뺀 값을 만들 수 있는 경우의 수
    //즉, 다음 코인에 해당하는 값을 더하면 결과가 되는 경우의 수에
    //현재에서 결과랑 같은 경우의 수를 더하면
    //해당 코인과 지금까지 이용했던 코인을 이용해서 해당 결과를 만드는 경우의 수가 된다.
    dp[0] = 1;
    for(int i = 1; i<=n; i++){
        //coin[i]부터 시작하는 이유는 그 전의 값은 어차피 걸러지기 때문
        for(int j = coin[i]; j<=k; j++){
                dp[j] = dp[j] + dp[j-coin[i]]; // dp[0]의 값을 추가시켜주어야한다.
        }
    }
    
    cout << dp[k];
}