1495번 – 기타리스트

문제

https://www.acmicpc.net/problem/1495

풀이

코드

from collections import deque

n, s, m = map(int, input().split())
diffs = list(map(int, input().split()))
visited = [[False]*101 for _ in range(1001)]
candidates = [-1]

def answer():
  global candidates
  DP()
  return max(candidates)

def DP():
  global n, s, m, diffs, candidates, visited
  Q = deque([(s, 0)])
  while(len(Q) > 0):
    volum, i = Q.popleft()
    if i >= len(diffs):
      candidates.append(volum)
      continue
    if visited[volum][i] is True: continue
    visited[volum][i] = True
    d = diffs[i]
    plus, minus = volum+d, volum-d
    if plus <= m: Q.append((plus, i+1))
    if minus >= 0: Q.append((minus, i+1))
      
print(answer())