[#29704] 벼락치기

문제

#29704 벼락치기
Gold5
적용 알고리즘: knapsnak 알고리즘

---

풀이 방법

• 일반적인 가방에 담기 문제이다.

코드 흐름

코드

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

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

for i in range(1, n + 1):
    for j in range(1, t + 1):
        weight = stuff[i][0] 
        value = stuff[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])

total_cost = 0
for i in range(len(stuff)):
    total_cost += stuff[i][1]

print(total_cost - knapsack[n][t])

체감 난이도: 4.2/5
이 유형의 문제는 여러번 풀어서 더 숙지해야 할거같다…