백준 12865 평범한베낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

첫 풀이

2차원 배열을 이용해서 풀음

dp[i][j]= i번째 물건까지 봤을때,  무계 j를 만족하는 가장 큰 가치

 

소스

import sys
input=sys.stdin.readline
n,k=map(int,input().split())

wv=[[0,0]]+[[*map (int,input().split())]for _ in range(n)]

dp=[[0 for _ in range(k+1)]for _ in range(n+1)]

#dp[i][j]=i번째 물건까지 봤을때, 무계가 j인 배낭의 최대가치

for i in range(1,n+1):
    for j in range(1,k+1):
        if j-wv[i][0]>=0:
            dp[i][j]=max(dp[i-1][j-wv[i][0]]+wv[i][1],
            dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]

print(dp[-1][-1])

그런데 다른사람들 풀이를 보다 보니, 2배는 효율적인 알고리즘이 있었다.

2차원 배열이 아니라 1차원 배열로 푸는 방식인데,

뒤에서부터 업데이트하면서 앞의 값을 쓰고, 계속 갱신시켜나가는 방법이다.

진짜 부족함을 느낀다.

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
dp=[0 for _ in range(k+1)]
# dp[i]= 무계가 i일때의 최댓값
for _ in range(n):
    w,v=map(int,input().split())
    for i in range(k,w-1,-1): #이전값들을 써먹기 위해뒤에서부터 돌면서
                            #만일 w>=k이면, 반복문안돔
        dp[i]=max(dp[i],dp[i-w]+v) 
        # 무계가 i일때의 최댓값은
        # {지금 주어진물건을 포함하지 않았을때의 최댓값과
        # 무계가 i-w 즉 지금물건을 포함할 수 있는 경우 +지금물건의 가치}
        # 의 최댓값이다.

print(dp[-1])

예제

4 7 #n,k
6 13
4 8
3 6
5 12

 

초기 dp

인덱스는 무계를 나타냄

0

0

0

0

0

0

0

0

6 13일때

7,8번째의 값이 변경됨

0

0

0

0

0

0

0

13

0

0

0

0

0

0

13

13

4 8일때

총 8,7,6,5를 돌면서 업데이트 (8,7은 13이 더 크니깐, 6,5만 업데이트)

0

0

0

0

0

8

13

13

0

0

0

0

8

8

13

13

3,6일때

마찬가지로 8에서 3까지 도는데, dp[8-3]+6이  14로 13보다 크므로, dp[8]업데이트

3업데이트

0

0

0

0

8

8

13

14

0

0

0

6

8

8

13

14

5 12일때

마찬가지로 8에서 5까지 도는데, dp[5-5]+12=0+12=12이므로,

5번째 인덱스 변경됨

0

0

0

6

8

12

13

14

우리가 찾는건 dp[i-1]