[백준] 1495 - 기타리스트

1. 문제

1495번: 기타리스트

2. 개요

dp문제.

3. 코드 및 추가내용

import sys

N, S, M = map(int, sys.stdin.readline().split())

v = list(map(int, sys.stdin.readline().split()))

dp = [S]

for i in range(N):
    l = [d + v[i] for d in dp if d + v[i] <= M] + [d - v[i] for d in dp if d - v[i] >= 0]
    dp = list(set(l))

print(max(dp)) if dp else print(-1)

시작 볼륨을 dp에 넣고 시작한다.

dp의 모든 값을 돌면서 +- v[i] 한 값이 0이상 M이하라면 리스트에 넣어두고 이 리스트를 다시 dp로 변환한다.

중복값이 있는 경우가 있으므로 한번 set으로 중복값을 없애준다.

끝까지 반복한 후 dp가 비어있다면 볼륨조절이 안되는 경우이므로 -1, 아니라면 최댓값을 출력한다.