[dp] 백준 1495 기타리스트

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

다이나믹 프로그래밍을 이용헤서 풀었습니다.

dp를 이차원 배열로 해서 그 곡에 가능한 볼륨을 체크하는 방식으로 풀었습니다.

#include <iostream>
using namespace std;
 
int main() {
    int n, s, m;
    bool dp[101][10001] = { {0,}, };
    int v[101];
    int ret = -1;
 
    cin >> n >> s >> m;
 
    for (int i = 1; i <= n; i++) cin >> v[i];
 
    if (s - v[1] >= 0) dp[1][s-v[1]] = true;
    if (s + v[1] <= m) dp[1][s+v[1]] = true;
 
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (dp[i - 1][j]) {
                if (j - v[i] >= 0) dp[i][j - v[i]] = true;
                if (j + v[i] <= m) dp[i][j + v[i]] = true;
            }
        }
    }
    
    for (int i = 0; i <= m; i++)
        if (dp[n][i]) ret = i;
    
    cout << ret;
 
}