백준 1495: 기타리스트

다이나믹 프로그램을 사용한다. 재귀적 방법을 사용했다. 연주가능하면 1 불가능하면 0 방식을 사용해 시작점부터 마치 분할 정복 하듯이 내려간다. 하지만 분할 정복은 아니다 왜냐하면 만약 같은 볼륨 값을 가르키는 지점에 여러 전 곡에서 도달했을 때 한 가지 경우만 세면 되기 때문이다. 

#include <iostream>
using namespace std;
int n, s, m;
int d[105][1005];
int v[105];
void go(int cur_n, int cur_vol)
{
    if (d[cur_n][cur_vol] != 0)
        return;
    d[cur_n][cur_vol] = 1;
    if (cur_n == n)
        return;
    if (cur_vol - v[cur_n + 1] >= 0)
    {
        go(cur_n + 1, cur_vol - v[cur_n + 1]);
    }
        
    if (cur_vol + v[cur_n + 1] <= m)
    {    
        go(cur_n + 1, cur_vol + v[cur_n + 1]);
    }
    return;
}
 
int main()
{
    cin >> n >> s >> m;
 
    for (int i = 1;i <= n; ++i)
        cin >> v[i];
    go(0, s);
    int ans = -1;
    for (int i = 0;i <= m; ++i)
    if (d[n][i] == 1)
        ans = i;
    cout << ans << endl;
    return 0;
}