BOJ 1495 - 기타리스트 링크
(2023.05.08 기준 S1)

문제

N개의 곡을 연주하는데, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i]로 연주해야 하며 0보다 작은 값이나 M보다 큰 값으로 볼륨을 바꿀 수 없다.
이 때, 마지막 곡을 연주할 수 있는 볼륨의 최댓값 출력

알고리즘

전형적인 DP

풀이

볼륨은 0부터 M까지 가능하다. M은 최대 1,000이고 곡은 최대 50개이므로 2차원 배열을 만들자.

직전 곡에 가능했던 볼륨으로 하여금 V[i]를 빼거나 더해서 범위 안이면 체크하여, 가능한 볼륨을 곡 차례대로 구해주면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

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

    int N, S, M;
    cin >> N >> S >> M;

    // 각각의 곡마다 가능한 볼륨을 체크
    bool dp[N + 1][M + 1]; memset(dp, false, sizeof(dp));
    dp[0][S] = true;

    for (int i = 1, v; i <= N; i++){
        cin >> v; // i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨
        for (int j = 0; j <= M; j++){
            if (dp[i - 1][j]){ // i-1번째 곡을 j 볼륨으로 연주가 가능했다면 j-v와 j+v 볼륨을 체크
                if (j - v >= 0) dp[i][j - v] = true;
                if (j + v <= M) dp[i][j + v] = true;
            }
        }
    }

    // N번째 곡의 연주 가능한 최대 볼륨을 찾아서 출력
    for (int i = M; i >= 0; i--) if (dp[N][i]){
        cout << i;
        return 0;
    }
    cout << -1;
}

• Python

import sys; input = sys.stdin.readline

N, S, M = map(int, input().split())
V = list(map(int, input().split()))

# 각각의 곡마다 가능한 볼륨을 체크
dp = [[0] * (M + 1) for _ in range(N + 1)]
dp[0][S] = 1

for i in range(1, N + 1):
    v = V[i - 1] # i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨
    for j in range(M + 1):
        if dp[i - 1][j]: # i-1번째 곡을 j 볼륨으로 연주가 가능했다면 j-v와 j+v 볼륨을 체크
            if j - v >= 0:
                dp[i][j - v] = 1
            if j + v <= M:
                dp[i][j + v] = 1

# N번째 곡의 연주 가능한 최대 볼륨을 찾아서 출력
for i in range(M, -1, -1):
    if dp[N][i]:
        print(i)
        break
else:
    print(-1)