[BOJ 1495] 기타리스트

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

DP문제이다. DP[i][j] 정의를 " i번째까지 사용하였을 때 j값을 만들수 있는가 없는가?" 로 정의하였다. 문제의 조건에 따라서 state값의 범위를 0이상 , m이하로 정의를 하고 pos가 n+1 까지 갔을때 state을 가지고 최대값을 가져왔다. 이번에도 재귀로 구현하였다. 근데 재귀 부분에서 ret = max(...)  이 부분 뭔가 깔끔하지가 않은데 이거 어케 해야될지 모르겠당 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define MAX_N 50
#define INF 1e8
 
typedef long long ll;
 
using namespace std;
 
int n,m,s,arr[111],ans,dp[111][1111];
 
 
int solve(int pos , int state){
    if(state>m || state<0)              //소리 범위가 0미만 , m 초과일떄
        return -INF;
    if(pos == (n+1)){                   //val값 (arr 시작이 1부터라 n+1)
        return state;
    }
    int &ret = dp[pos][state];
    
    if(ret != -1)
        return ret;
    
    ret = -INF;
    ret = max(ret , solve(pos+1, state-arr[pos]));
    ret = max(ret , solve(pos+1 , state+arr[pos]));
    return ret;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ans = 0;
    memset(dp,-1,sizeof(dp));
    cin >> n >> s >> m;
    
    for(int i=1;i<=n;i++){
        cin >>arr[i];
    }
    int ans = solve(1,s);
    if(ans < 0){
        cout << "-1\n";
    }else{
        cout << ans <<endl;
    }
    
    return 0;
}