[백준 1495] 기타리스트

0. 제목

• 백준 1495 기타리스트
• BOJ 1495 기타리스트
• 파이썬 1495 기타리스트
• Python 1495 기타리스트

---

1. 문제

www.acmicpc.net/problem/1495

1495번: 기타리스트

---

2. 풀이

• 0부터 m까지의 볼륨이 가능하고 각 볼륨에서 출력이 가능하면 True, 불가능하면 False로 설정한다.
• dp[i][j + 1] : i 번째 노래일 때 j 크기의 볼륨으로 연주 가능한지 여부
• 노래를 순서대로 확인하며, 매 번 모든 크기의 볼륨에 대하여 검사한다.
• dp[n]의 원소 값들 중 True이면서 가장 큰 index를 출력한다.

---

3. 코드

n, s, m = map(int, input().split())  
v = list(map(int, input().split()))
 
dp = [[False] * (m + 1) for _ in range(n + 1)]
 
dp[0][s] = True
 
for i in range(1, n + 1):
    for j in range(0, m + 1):
        if dp[i-1][j] == 0:
            continue
            
        if j - v[i-1] >= 0:
            dp[i][j-v[i-1]] = True
        
        if j + v[i-1] <= m:
            dp[i][j+v[i-1]] = True
 
result = -1
for i in range(m, -1, -1):
    if dp[n][i] == True:
        result = i
        break
        
print(result)