March 2, 2023

1495번: 기타리스트

문제 요약

• 공연에서 매번 곡이 시작하기 전 볼륨을 바꾸고 연주하려 한다.
• 현재 볼륨이 P이고 지금 i번쨰 곡을 연주하기 전이라면, i번 곡은 P + V[i]나 P - V[i]로 연주해야 하고, 0보다 작은 값으로 볼륨을 바꾸거나 M보다 큰 값으로 볼륨을 바꿀 수 없다.

풀이

N, S, M = map(int, input().split())
range_list = [0] + list(map(int, input().split()))
dp = [[False] * (M + 1) for _ in range(N + 1)]
dp[0][S] = True

for i in range(1, N + 1):
    for j in range(0, M + 1):
        if (j - range_list[i] >= 0 and dp[i - 1][j - range_list[i]]):
            dp[i][j] = True
        elif (j + range_list[i] <= M and dp[i - 1][j + range_list[i]]):
            dp[i][j] = True

max_idx = -1

for i in range(0, M + 1):
    if (dp[N][i]):
        max_idx = i

print(max_idx)

• 1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M
• 배열에 i 번째 공연일 때 볼륨이 j인 것이 가능한지 여부를 저장