이번 문제는 다이나믹 프로그래밍을 활용하여 해결하였다. 여태 풀었던 다이나믹 프로그래밍과 조금 다르게 메모라이제이션을 하였다. (n+1)*(m+1)의 리스트를 만들고 n을 순회하면서 리스트를 한줄씩 거치게 된다. 순회 전에 dp[0][s]를 1로 바꿔준다. 그리고 반복을 통해서 볼륨이 가능한 위치의 원소를 모두 1로 갱신시켜주고 dp[-1] 리스트를 확인하면서 1로 체크되어 있는 가장 큰 인덱스를 정답으로 출력하였다.

점화식은 dp[i-1][j]이 1일 때, dp[i][j+v[i-1]]=1, dp[i][j-v[i-j]]=1이다.

• n, s, m을 입력받는다.
• v 리스트를 입력받는다.
• dp를 (n+1)*(m+1) 리스트로 선언하고 0으로 채운다.
• dp[0][s]를 1로 갱신한다. (현재:0 일때의 볼륨은 s이므로)
• 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> m까지 반복하는 j에 대한 for문을 돌린다.
  --> 만약 dp[i-1][j]가 0이라면 다음 반복을 진행한다.
  --> 만약 j+v[i-1]이 m보다 작거나 같을 경우, dp[i]j+v[i-1]]을 1로 갱신한다.
  --> 만약 j-v[i-1]이 0보다 크거나 같을 경우, dp[i]j-v[i-1]]을 1로 갱신한다.
• m부터 0까지 반복하는 감소하는 i에 대한 for문을 돌린다.
  -> 만약 dp[-1][i]가 1일 경우 i를 출력하고 반복문을 탈출한다.
• 이 외에는 -1을 출력한다.

Code

n, s, m=map(int, input().split())
v=list(map(int, input().split()))
dp=[[0]*(m+1) for _ 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:
            continue
        if j+v[i-1]<=m:
            dp[i][j+v[i-1]]=1
        if j-v[i-1]>=0:
            dp[i][j-v[i-1]]=1
for i in range(m, -1, -1):
    if dp[-1][i]==1:
        print(i)
        break
else:
    print(-1)