[PY] 12865 : 평범한 배낭

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

점화식 세우지 못한 상황을 받아들이고 그냥 한 번 아이디어 보면서 만들어보니 되긴 되더라.

근데 막판에 인덱스 관련해서 좀 많이 얼타가지고 파일럿 코가 해결해주었다.
어느 순간 파일럿 코에게 코드의 끝 마무리 할 기회를 던지는 것 같아서 기분이 안좋다. 처음부터 끝까지 내가 한 코드가 있는걸까.

핵심 식은 2차원 배열에 각 가방과 짐에 대한 점진적 배치 또는 증가 식을 놓는다.

• 담을 수 없어?
  • 그럼 [i - 1][j] 과 동일하다.
• 담을 수 있어?
  • 그럼 [i - 1][j] 랑 해당 아이템을 포함한 데이터를 구성하여 그 중 더 많은 가치의 값으로 구성한다.
    • itemList[j].value + bag[i - itemList[j].kg][j] 뭐 이런식.. 
    • 중요 한 것은 value가 빠진 만큼 bag은 그 value가 빠진 영역에서 내용을 찾아온다는 것이다.

 

실패한 코드

import sys
input = sys.stdin.readline

itemCount, backPackStatus = map(int, input().split())
itemList = []
maxBagUse = [[0] * (itemCount) for _ in range(backPackStatus + 1)]

for i in range(itemCount):
    kg, value = map(int, input().split())
    itemList.append([kg, value])
    # 이렇게 되면 itemList[n]의 [0]은 kg, [1]은 value가 된다.


for i in range(1, backPackStatus + 1):
    for j in range(itemCount):
        if(itemList[j][0] > i):
            maxBagUse[i][j] = maxBagUse[i][j - 1]
        else:
            maxBagUse[i][j] = max(maxBagUse[i][j - 1], itemList[j][1] + maxBagUse[i - itemList[j][0]][j - 1])

print(maxBagUse[backPackStatus][itemCount - 1])

 

통과 코드

import sys
input = sys.stdin.readline

itemCount, backPackStatus = map(int, input().split())
itemList = []
maxBagUse = [[0] * (itemCount + 1) for _ in range(backPackStatus + 1)]  # itemCount + 1로 수정

for i in range(itemCount):
    kg, value = map(int, input().split())
    itemList.append([kg, value])

for i in range(1, backPackStatus + 1):
    for j in range(1, itemCount + 1):  # j를 1부터 시작하도록 수정
        if itemList[j - 1][0] > i:
            maxBagUse[i][j] = maxBagUse[i][j - 1]
        else:
            maxBagUse[i][j] = max(maxBagUse[i][j - 1], itemList[j - 1][1] + maxBagUse[i - itemList[j - 1][0]][j - 1])

print(maxBagUse[backPackStatus][itemCount])