[백준 1495/파이썬(Python)] 기타리스트(실버 1)

https://www.acmicpc.net/problem/1495

1495번: 기타리스트

 

💜풀이

---

1. 곡 개수(n, 행)만큼 최대 볼륨값(m, 열) 길이의 배열을 만든다.
2. d[i][j]=i 번째 곡을 j만큼의 볼륨으로 연주할 수 있는지의 여부
3. 첫 시작 부분, 즉, d[0][s]를 1로 설정한다.
4. 이중 루프 돌면서 만약 이전 곡의 현재 볼륨 위치에 1로 체크가 되어 있으면 현재 곡도 볼륨을 조정해서 연주할 수 있다. 다시 말해, 이전 곡의 볼륨 위치에 설정되어 있는 볼륨을 조정해 저장할 수 있다.
5. 설정한 볼륨 j+=v[i-1]가 범위 내라면 그 위치를 1로 체크한다.
6. 루프 돌면서 가장 마지막 행의 값이 1인 것 중에서 인덱스가 최대인 곳을 찾아 출력한다.

---

💜코드

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:
            if 0<=j+v[i-1]<=m:
                dp[i][j+v[i-1]]=1
            if 0<=j-v[i-1]<=m:
                dp[i][j-v[i-1]]=1

answer=-1
for i in range(m+1):
    if dp[n][i]==1:
        answer=max(answer,i)

print(answer)