백준 1495 기타리스트 (C++)

1495번: 기타리스트

dp를 이용한 문제이다. 처음에는 단순히 dfs로 접근을 해볼려고 했는데 시간 초과가 날 것 같아 dp로 구현을 했다. 로직은 간단하다. 음악, 볼륨을 나타내는 이중 배열을 만들어 반복문을 통해 이전 음악의 볼륨에서 더했을 때와 뺐을 경우가 각각 조건에 만족할 경우 true로 선언해준다. 그 후 마지막 음악 중 true인 볼륨 배열 중에서 가장 큰 값을 구해 출력해주고 true가 없을 경우 -1을 출력하였다. 어렵지 않게 풀 수 있었던 문제였다.

#include <iostream>

using namespace std;

int N, S, M;
int V[51];
bool dp[51][1001];
int result = -1;

void solution() {
    if (S + V[1] <= M) dp[1][S + V[1]] = true;
    if (S - V[1] >= 0) 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]) continue;

            if (j + V[i] <= M) dp[i][j + V[i]] = true;
            if (j - V[i] >= 0) dp[i][j - V[i]] = true;
        }
    }

    for (int i = M; i >= 0; i--) {
        if (dp[N][i]) {
            result = i;
            break;
        }
    }

    cout << result;
}

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

    cin >> N >> S >> M;

    for (int i = 1; i <= N; i++) {
        cin >> V[i];
    }

    solution();

    return 0;
}