인프런 커뮤니티 질문&답변

이제 DP도 다 들어 가시는군요!!! 기쁩니다!!! ( 탑다운 디피 질문 없이 바로 바텀업까지..!! 빠르게 성장을 하고 계시군요!! )

아래 도움이 되실까 싶어서 코드를 한번 보기 쉽게 바꿔봤습니다! ( 정답 코드는 제가 빼먹고 안넣었네요..! )

import sys
input = sys.stdin.readline

# 입력 받기
ItemNumber, MaxBagWight = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(ItemNumber)]
dp = [[0 for _ in range(MaxBagWight+1)] for _ in range(ItemNumber+1)]

# 물건을 하나씩 고릅니다.
for ItemIndex in range(ItemNumber):
    ItemWeight = items[ItemIndex][0]
    ItemValue = items[ItemIndex][1]
    # 가방 무게가 0일때부터 최대무게일때까지 가정합니다.
    # ( 무게를 모두 사용하지 않아도 정답인 경우가 있을 수 있음 )
    for BagWeight in range(MaxBagWight+1):
        # 조건문
        # 물건을 가방에 담을 수 없다면 전에 넣어뒀던 무게로 유지
        if BagWeight < ItemWeight:
            dp[ItemIndex][BagWeight] = dp[ItemIndex-1][BagWeight]
        # 그 외
        # 물건을 넣을 수 있다면 넣어보고 무게 비교하기
        else:
            dp[ItemIndex][BagWeight] = max(
                dp[ItemIndex-1][BagWeight-ItemWeight] + ItemValue, dp[ItemIndex-1][BagWeight])


print(items)
print(dp)
print(dp[ItemNumber-1][MaxBagWight])

문제는 10:55초 입니다. 작성하신 코드는 if weight < B 인데요. 부연 설명은 "가방의 무게보다 작으면 예외 처리를 한다"라고 이해했습니다. 문제의 요구사항에 따르면 가방의 무게보를 초과했을 때 예외처리를 해야 하지 않나? 라는 의문이 들었는데요. 아직 의문을 해결하지 못하여 선생님의 코드가 잘 이해가 되지 않는 상태에 있습니다...

남은 가방 무게보다 아이템 무게가 클 때 예외처리를 하는 것임으로 [BagWeight < ItemWeight] 이해하신 바가 맞습니다! 언급하신 부분이 단순하게 탑다운>바텀업 변환을 하면서 설명하는 부분이라 설명에 생략이 있어서 그렇습니다..!

위 코드로 한번 더 풀어보시고 어려우시면 또 답글 남겨주세요!

항상 질문 보내주시는 거 보면서 큰 힘이 되고 있습니다 ㅎㅎ

신년도 화이팅입니다! ( 혹시 앱강의도 관심이 있으시다면 지금 만들고 있는데 나중에 무료로 보내드릴테니 꼭 한번 들어봐주세요! )