백준 1495) 기타리스트 (python)

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

1495번: 기타리스트

 

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(n):
    for j in range(m+1):
        if dp[i][j] == 1:
            n1 = v[i] + j
            n2 = j - v[i]

            if n2 >= 0:
                dp[i+1][n2] = 1
            if n1 <=m:
                dp[i+1][n1] = 1
res = -1
for i in range(m, -1, -1):
    if dp[n][i] == 1:
        res = max(res, i)
print(res)

 

2차원 배열을 사용하는 문제이다

 

나는 1차원 배열로 생각해서 풀었다. 다만 문제 이해가 어려워서 못풀고 해설을 봤다...

 

 

이 문제는 

 

1. 두번째 줄 주어지는 볼륨차이를 계산해서 2차원 dp에 값을 저장하는 것이다

-> 여기서 만일 볼륨차이값보다 크거나 0보다 더 작으면 그냥 넘어감(기록을 안함)

 

2. 배열 끝부분만 탐색해서 1인 값중에 가장 큰값을 넣어서 리턴함

 

내가 못푼 이유

2차원 dp를 떠오르게 하는 것이 안됬다.. 아직도 잘 모르겠다

아시면 덧글로...