백준 5557번. 1학년(c++) / dp

흠... 골드5인데,,,참 어렵다...아직 글쓴이는 dp가 어려운 것 같다...^^

그래서 구글에 검색해서 나온 코드를 읽어가며 이해하고 다시 풀었다.

 

8+3-2-4+8-7-2-4-0+8=8 이러한 식이 있을 때에

dp[지금까지의 합][현재 idx] 이렇게 저장했다.

맨 처음 idx=0일때는, dp[8][0] += (dp[11][1]+dp[5][1]) 그 다음의 수를 더한 경우와 그 다음 수를 뺀 경우를 모두 더한 값이다.

주절주절....코드를 보시면 더 이해하기 쉬울 것이다.

 

코드 첨부

// 1학년
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int n, m;
vector<int> v;
long long dp[21][102] = {0, }; // 가능한 개수
 
long long go(int sum, int idx)
{
    if(sum>20 || sum<0){
        return 0;
    }
 
    if(idx==n-2){
        if(sum==v[n-1]){
            return 1;
        }else{
            return 0;
        }
    }
 
    long long &num = dp[sum][idx];
 
    if(num!=-1){
        return dp[sum][idx];
    }
 
    num = 0;
 
    // 더할 경우와 뺄 경우의 수를 모두 더해준다.
    return num += (go(sum+v[idx+1], idx+1)+go(sum-v[idx+1], idx+1));
}
 
int main()
{
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>m;
        v.push_back(m);
    }
 
    memset(dp, -1, sizeof(dp));
 
    cout<<go(v[0], 0)<<"\n";
 
    return 0;
}

 

 

문제 첨부

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

5557번: 1학년