dp를 2차원으로 확장시켜야... (#12865)

#12865 평범한 배낭 https://www.acmicpc.net/problem/12865

 

과거 풀다가 해결을 못해서 버렸던 문제다.

 

 

틀린코드

n, k = map(int, input().split())

dp = [0] * (k + 1)

obj = []

for _ in range(n):
    w, v = map(int, input().split())
    dp[w] = v
    obj.append([w, v])

for i in range(k + 1):
    for w, v in obj:
        if i + w <= k:
            dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))

 

왜 자꾸 틀릴까? 의문이었다..

 

 

근데 잘 생각해보니, 물품의 중복이 가능한 코드였다. 

주어진 테스트케이스에서 극단적인 상황을 가정해보자.

무게 1, 가치 100짜리 물건이 있다면 어떻게 될까

이렇게, 그 물건을 7개 담아버리면 가장 높은 가치가 된다. 이는 잘못된 로직이다.

 

물건이 중복되면 안된다. 따라서 담은 물건을 기록하는 리스트를 추가해 dp를 만들었다.

 

 

정답코드

import copy

n, k = map(int, input().split())

dp = [[0, []] for __ in range(k + 1)]
# [[value, [담은 물품의 flag]],  ......]
obj = []

for i in range(n):
    w, v = map(int, input().split())
    # dp[w][0] = v
    # dp[w][1][i] = True
    obj.append([w, v])

for prev_weight in range(k + 1):
    for i in range(n):
        w, v = obj[i]
        if prev_weight + w <= k:
            visited = dp[prev_weight][1]
            if i not in visited:
                if dp[prev_weight][0] + v > dp[prev_weight + w][0]:
                    value = dp[prev_weight][0] + v
                    dp[prev_weight + w] = [value, visited + [i]]

dp.sort(key=lambda x: x[0])

print(dp[-1][0])

 

이렇게 해결할 수 있었다.

 

근데 뭔가 찝찝해서 다른 사람들의 정답을 찾아보았다.

 

https://velog.io/@js43o/%EB%B0%B1%EC%A4%80-12865%EB%B2%88-%ED%8F%89%EB%B2%94%ED%95%9C-%EB%B0%B0%EB%82%AD

[백준] 12865번: 평범한 배낭

 

2차원 리스트로 만드는게 정석이었던 것 같다 ㅋㅋㅋ

 

물건의 중복이 안되는 상황이라면, 무게 / 아이템 형태의 2차원 리스트가 더 올바른 접근법일 것 같다. (시간복잡도 해결!)

 

 

또한, 문제가 안풀릴 때에는 극단적인 테스트케이스를 생각해볼 필요가 있는데..

새로운 케이스를 만들기 보다는 기존의 테스트케이스에 새로운 값을 추가하는 방법도 좋은 접근인 것 같다.

 

뭐랄까,,, 일종의 "테스트 케이스 파생법"?.. 뭐 이런 생각이 들었다.