[BOJ] 12865 평범한 배낭

# 12865 평범한 배낭



N,K = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(N)]

dp = [0]*(K+1)
for i in range(N):
    weight,value = arr[i]
    for k in range(K,-1,-1):
        if k + weight <= K:
            if k == 0:
                dp[k+weight] = max(dp[k+weight],dp[k]+value)
            else:
                if dp[k]:
                    dp[k+weight] = max(dp[k+weight],dp[k]+value)
print(max(dp))

아마 동적프로그래밍 관련 유명한 문제인걸로 알고 있다.

풀어보고 다른 사람 코드를 보니깐, 2개의 리스트를 만들어서 하나는 최대값이 되는 값을 저장하는 리스트와, 사용여부를 나타내는 리스트를 2개를 두고 하는 경우가 많았다.

 

그러나 나같은 경우엔 한가지 리스트를 주고, dp의 인덱스값이 0일때는 최대 무게를 넘지 않는한 바로 더해주었고, 그 외에는 해당 인덱스에 저장된 값이 존재하는 경우에만 하도록 했다. 이렇게 했을시에 사용여부를 따로 만들지 않아도 되었다.

 

여기서 중요했던 점은 역으로 판단을 해줘야했던 것이다. 앞에서부터 순서대로 할시에, 그대로 그 전거가 다음거에 영향을 주기 때문에 끝에서 0으로 가는 것이 중요했다.