[DP] 백준 5557 1학년

•   상한, 하한이 있는 문제 (sum은 중간에 0 에서 20 사이를 벗어나면 안되었다.)
•   이것 때문에 dp 시작을 idx = 0, sum = 0 에서 하면 안되고 idx = 0 에서는 무조건 더하기만 가능했기 때문에 이를 구현하기 위해서 시작을 idx = 1, sum = tb1[0] 으로 해주어야 했다.
•    1차원 cache로 구현하려고 오랫동안 고민했는데 ( 2차원으로 하는 문제란 걸 모르고 ) 2차원 배열로 sum의 경우까지 구분해 주어야 하는 것을 생각하지 못했었다. 질문 보기를 통해 알았다. idx 만으로 구분하기엔 뭔가 찜찜한 느낌은 있었는데 제대로 안 것 같다. 

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <cstring>

#include <stack>

#include <queue>

#include <limits.h>

using namespace std;

typedef long long ull;

int n;

int tb1[111];

ull che1[110][21];

ull go(int idx, int sum){

    if(idx == n-1 && sum == tb1[idx]){

        return 1;

    }

    else if(idx == n-1){

        return 0;

    }

    if(sum > 20){

        return 0;

    }

    if(sum < 0){

        return 0;

    }

    ull& ret = che1[idx][sum];

    if(ret != -1){

        return ret;

    }

    ret = 0;

    ret = go(idx+1,sum+tb1[idx]) + go(idx+1,sum-tb1[idx]);

    return ret;

}

int main(void){

    memset(che1,-1,sizeof(che1));

    cin >> n;

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

        cin >> tb1[i];

    }

    cout << go(1,tb1[0]) << endl;

    

    return 0;

}