[백준] 1495 기타리스트

1495번: 기타리스트

 

www.acmicpc.net

풀이

동적계획법 문제이다. 이차원배열 dp[i][j]에서 i번째 곡의 볼륨 j가 가능한지를 체크해주는 방식으로 해결했다.

코드

#include <iostream>
using namespace std;

int n, s, m;
int v[100];
bool dp[100][1001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> s >> m;
    for (int i = 0; i < n; i++) 
        cin >> v[i];

    if (s + v[0] <= m) dp[0][s + v[0]] = true;
    if (s - v[0] >= 0) dp[0][s - v[0]] = true;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            if (!dp[i - 1][j]) continue;

            if (j + v[i] <= m)
                dp[i][j + v[i]] = true;                

            if(j - v[i] >= 0)
                dp[i][j - v[i]] = true;
        }
    }

    int ans = -1;
    for (int i = 0; i <= m; i++) {
        if (!dp[n - 1][i]) continue;
        ans = i;
    }
    cout << ans << '\n';
    return 0;
}