🦊 기타리스트

1. 문제 링크

1495번: 기타리스트

2. 코드

Python3 메모리: 31256kb 시간: 56ms

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

dp = [[0 for j in range(M + 1)] for i in range(N + 1)]

dp[0][S] = 1
for i in range(N):
    for j in range(M + 1):
        if dp[i][j] == 1:
            up = j + volumes[i]
            down = j - volumes[i]
            
            if 0 <= up <= M:
                dp[i + 1][up] = 1
            if 0 <= down <= M:
                dp[i + 1][down] = 1

ans = -1
for i in range(M + 1):
    if dp[N][i] == 1:
        ans = i
print(ans)

• 해설

  dp[N][volume] = N 번째에서 volume 으로 설정 가능한지 여부

  체크된 값을 찾아서 가능할 경우 더하고 빼면서 최대값을 마지막에 구함