[Python] 백준 1495번: 기타리스트

# 문제 내용

백준 1495번: 기타리스트 

1495번: 기타리스트

 

# 알고리즘 분류

• 다이나믹 프로그래밍

 

# 풀이

import sys
input = sys.stdin.readline

# n : 곡 수
# s : 시작 볼륨
# 0 < 볼륨 최대 값 < m 
n, s, m = map(int, input().split())

# 곡 순서에서 변경할 수 있는 볼륨 차
v = list(map(int, input().split()))

# 2차원 배열로 각 곡마다 가능한 볼륨 저장
dp = [[0] * (m+1) for _ in range(n+1)]

# dp[0][5] = 1 일 경우, 0번째 곡의 볼륨이 저장되어있고 5라는 뜻
dp[0][s] = 1

for i in range(n):
  for j in range(m+1):
    # 현재 i곡의 볼륨이 담겨있으면
    if dp[i][j] == 1:
      min_val = j - v[i]
      max_val = j + v[i]
      # 줄인 볼륨이 0보다 크거나 같을 경우 다음 곡에 현재 볼륨 담기
      if min_val >= 0:
        dp[i+1][min_val] = 1
      
      # 키운 볼륨이 m보다 작거나 같을 경우 다음 곡에 현재 볼륨 담기
      if max_val <= m:
        dp[i+1][max_val] = 1

result = -1
# 반복문을 통해 끝부터 확인해 최대값 출력
for i in range(m, -1, -1):
  if dp[n][i] == 1 :
    result = i
    break
print(result)