12865 - 평범한 배낭

머리 굴리는데, DP 만한 문제는 없죠

 

근데 못 품 ㅎ;; 답 봄 ㅎ;;

 

항상 DP는 푸는 법을 알고나면, 너무나 쉬운거 같아요.

---

 

목표 : 가방에 가치가 가장 높게 물건을 넣는 방법 찾기

 

접근 : 가방에 물건을 넣는 경우의 가치, 가방에 물건을 안 넣는 경우의 가치를 비교하자

 

접근 방법만 알면 간단합니다.

 

물건은 총 100 개, 무게는 100,000이며, 시간 복잡도는 10,000,000이며 시간 제한은 2초니 충분하겠네요.

 

배열을 만들어봅시다. index가 가방의 무게인 배열을요. 그 안에 들어가는 값은 가치입니다.

 

즉, 물건 순서대로 가방의 무게(index)마다, 최고의 가치를 넣어주면 됩니다.

N, K = list(map(int, input().split()))

DP = [0 for k in range(K + 1)]

for n in range(N):
    W, V = list(map(int, input().split()))
    for k in range(K, -1, -1): # 뒤에서부터 쟀는데, 앞에서 부터 비교하면 현재의 값이 비교에 방해되기 때문
        if k - W >= 0:
            DP[k] = max(DP[k - W] + V, DP[k])

print(DP[-1])

역시 답을 알고나면 간단한 DP ;;

 

그래서 싫어

 

흥