백준 1495 / 기타리스트

지금 5로 연주하고 있고, 다음 곡의 볼륨이 2라면

다음곡은 3과 7로 연주할 수 있다.

D[n][i]가 n번쨰 곡에서 볼륨 i로 연주 할 수 있으면 1, 없으면 0이라고 하자.

처음 볼륨이 s라면 

D[0][s]=1이고,

첫번째 곡의 볼륨이 3이라면

D[1][s-3] = 1 , D[1][s+3] =1이 되는 식이다.

여기서 s-3이 0보다 크거나 같아야 되고

s+3이 m보다 작아야한다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int d[102][1002];
int v[101];
 
int main() {
    
    //freopen("Text.txt", "r", stdin);
 
    int n, s, m;
 
    cin >> n >> s >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
 
    d[0][s] = 1;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
 
            if (d[i][j] == 1) {
                if (j - v[i + 1] >= 0) {
                    d[i + 1][j - v[i + 1]] = 1;
                }
                if (j + v[i + 1] <= m) {
                    d[i + 1][j + v[i + 1]] = 1;
    
                }
            }
        }
    }
 
    int ans = -1;
 
    for (int i = 0; i <= m; i++) {
        if (d[n][i] == 1) {
            ans = i;
        }
    }
 
    cout << ans << endl;
 
}