[Baekjoon]백준 12865 평범한 배낭(골드 5) - Python

문제설명

문제를 읽어보면 배낭에 최대한 많은 가치를 가져갈 수 있도록 가방의 무게에 따라 적절하게 물건을 넣어야한다

이 문제는 DP를 사용한 알고리즘의 예시 중 하나이다

이번에도 다른 문제들처럼 하나의 2차원 리스트를 만들고, 이를 채워나가면서

앞서 계산한 결과와 다음칸 계산결과, 현재 계산결과 중에서 최댓값을 찾아 값을 갱신해나가는 방식이다

num, weight = map(int, input().split())
result = [[0] * (weight + 1) for _ in range(num + 1)]
bag = []

for _ in range(num):
    bag.append(list(map(int, input().split())))
    
for i in range(1, num + 1):
    for j in range(1, weight + 1):
        if j >= bag[i-1][0]:
            result[i][j] = max(result[i-1][j], result[i][j-1], result[i-1][j-bag[i-1][0]] + bag[i-1][1])
        else:
            result[i][j] = result[i-1][j]
            
print(result[num][weight])

일단 가방의 정보를 담을 리스트 하나와, 결과값을 저장할 리스트를 하나 만들어준다

이후에 for문 두개를 통해 확인하면 되는데, 해당 index의 가방의 무게가 최대 무게보다 작다면 지금 index의 가방의

무게를 선택하지 않은 경우, 이전 물건들로 이루어진 경우, 현재 아이템을 선택한 경우 세 가지 중에서

최댓값을 찾아 이를 저장하면 된다 만약 현재 물건의 무게가 가방의 최대 무게보다 크다면

현재 index의 물건을 선택할 수 없기 때문에 이전 결과값을 넣어주면 된다

이러한 로직으로 작성하면 제일 마지막 index에 최대값이 저장되므로 이를 출력해주면 정답임을 확인할 수 있다