(C++) 백준 1495 기타리스트

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

처음에 너무 무지성으로 재귀 쓰면 되지 않나?
생각했다 ㅠ
시간초과가 왜 날까 했는데

다시 생각해보면 재귀가 호출되는것은
P+V[i]나 P-V[i] 뿐만 아니라
P+V[i-1]+V[i], P+V[i-1]-V[i], P-V[i-1]+V[i], P-V[i-1]-V[i] 이런식으로
n번째에서 2의 n승 만큼 호출된다
따라서 DP로 풀어야 한다.
table을 만들어서 이전에 만들어진적이 있는값(true)에 대해서만 처리를 해주면
2중 for문으로 문제를 풀 수 있다

#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
int N,M,S;
int ans=-1;
bool dpTable[1005][105];

// 이전이 두개가 아니라 여러개


int main(){


    cin>>N>>S>>M;

    // 개수, 시작, 최대
    //0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

    int x;
    for(int i=0; i<N; i++) {
        cin>>x;
        v.push_back(x);
    }

    if(S+v[0]<=M) dpTable[S+v[0]][0]=true;
    if(S-v[0]>=0) dpTable[S-v[0]][0]= true;

    for(int i=1; i<N; i++){

        for(int j=0; j<=M; j++){

            if(!dpTable[j][i-1]) continue;

            if(j+v[i]<=M) dpTable[j+v[i]][i]=true;
            if(j-v[i]>=0) dpTable[j-v[i]][i]=true;

        }

    }


    for(int i=M; i>=0; i--){
        if(dpTable[i][N-1]) {
            ans=i;
            break;
        }
    }

    cout<<ans;
}