BOJ - 1495

백준 문제 링크
기타리스트

❓접근법

1. 0 ~ M까지를 가지는 M+1 길이를 가진 리스트 N+1 개를 만든다. (DP)
   예제 1번에서는 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <- 이 리스트가 4개
2. 초기값 DP[0][S] = 1로 지정한다. (방문한 것과 동일)
   볼륨의 정보를 리스트 volume으로 받는다.
3. 조건은 다음과 같다.

• for i in range(1, N+1):
  • for j in range(M+1):
    • if DP[i-1][j] != 0:
      • if 0 <= j + volume[i-1] <= M:
        • DP[i]j + volume[i-1]] = 1 (볼륨을 더했을 때 방문처리)
      • if 0 <= j - volume[i-1] <= M:
        • DP[i]j - volume[i-1]] = 1 (볼륨을 뺐을 때 방문처리)

4. 위의 조건대로 실행하면 DP는
   [[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
   [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
   [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
   [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]로 나올 것이다.
5. 우리가 구해야 하는 것은 마지막 곡 까지 도달했는지와,
   도달했을 때의 최대 볼륨을 구하는 것이다.
6. 따라서
   isFalse = False, answer = 0으로 지정 후
   DP[N]에서 인덱스를 내림차순으로 살펴보며
   1이 있다면 answer = i, isFalse = True로 지정한 후 break 해준다.
7. isFalse가 True이면 answer를, False이면 -1을 출력하면 끝!

👌🏻코드

N, S, M = map(int, input().split())

volume = list(map(int, input().split()))

DP = [[0] * (M+1) for i in range(N+1)]
DP[0][S] = 1

for i in range(1, N+1):
   for j in range(M+1):
       
       if DP[i-1][j] != 0:
           if 0 <= j + volume[i-1] <= M:
               DP[i][j + volume[i-1]] = 1
               
           if 0 <= j - volume[i-1] <= M:
               DP[i][j - volume[i-1]] = 1
               

isFalse = False
answer = 0
for i in range(M, -1, -1):
   if DP[N][i] == 1:
       answer = i
       isFalse = True
       break
       
if isFalse == True:
   print(answer)
else:
   print(-1)