[BOJ] 1495. 기타리스트

---

문제 링크

---

import sys
input = sys.stdin.readline

n, s, m = map(int, input().split())
gap = [s] + list(map(int, input().split()))

# [곡번호][볼륨크기]
dp = [[False for _ in range(m + 1)] for _ in range(n + 1)]

def check_range(vol):
  if vol < 0 or vol > m:
    return False
  return True

if check_range(s - gap[1]):
  dp[1][s - gap[1]] = True
if check_range(s + gap[1]):
  dp[1][s + gap[1]] = True

for i in range(1, n):
  for j in range(m + 1):
    if dp[i][j]:
      if check_range(j + gap[i + 1]):
        dp[i + 1][j + gap[i + 1]] = True
      if check_range(j - gap[i + 1]):
        dp[i + 1][j - gap[i + 1]] = True

check = False
for i in range(m, -1, -1): # 범위 조심,,, (m, 0, -1) 했
  if dp[n][i]:
    print(i)
    check = True
    break

if not check:
  print(-1)

(1 ≤ N ≤ 100, 1 ≤ M ≤ 1000) -> DP 생각하자
범위를 봐서 DP가 가능한지 생각해보자

첨에 deque로 구현했다가 1퍼에서 메모리 초과 나옴
글고 for문 범위 조심(91%에서 탈락)

---

21.06.28 복습

import sys  
input = sys.stdin.readline

n, s, m = map(int, input().split())
v = list(map(int, input().split()))

dp = [[False for _ in range(m + 1)] for _ in range(n)]
# dp[index][volume]
if s + v[0] <= m:
  dp[0][s + v[0]] = True
if s - v[0] >= 0:
  dp[0][s - v[0]] = True

for i in range(n - 1):
  for j in range(m + 1):
    if dp[i][j]: # 
      if j + v[i + 1] <= m:
        dp[i + 1][j + v[i + 1]] = True
      if j - v[i + 1] >= 0:
        dp[i + 1][j - v[i + 1]] = True

for vol in range(m, -1, -1):
  if dp[n - 1][vol]:
    print(vol)
    exit(0)
    
print(-1)

음 일단 참고하면서 풀었다.. 다시 한번 더 풀기를.