[백준] 12865번 평범한 배낭 - 파이썬 (Python)

 

문제링크: https://www.acmicpc.net/problem/12865 

12865번: 평범한 배낭

 

    import sys
    input = sys.stdin.readline

    n, k = map(int, input().split())
    item = [[0, 0]]
    knapsack = [[0 for _ in range(k + 1)] for _ in range(n + 1)]

    for _ in range(n):
        item.append(list(map(int, input().split())))


    for i in range(1, n + 1):
        for j in range(1, k + 1):
            weight = item[i][0]
            value = item[i][1]

            if j < weight:                              #무게가 안될시 그 전단계까지의 최대 밸류를 끌어온다
                knapsack[i][j] = knapsack[i - 1][j]
            else:                                       #무게가 되면, 그때까지 담을 수 있는 최대 밸류를 정해준다
                knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])

    print(knapsack[n][k])

 

냅색(knapsack) 문제입니다. 이런 류의 문제는 자주 보는 것 같아 한줄 한줄 이해해야하는 것 같네요.
https://claude-u.tistory.com/208 이 분의 코드에서 많은 도움을 받았습니다. 표를 그려주셔서 이해하는데 도움이 됐네요. 다양한 패턴의 문제를 머릿속에 넣어가는 중입니다.