[백준 12865] DP 유형 : 01타일(python 풀이)01타일

1. 문제 

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

2. 입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

3. 출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

---

4. 포인트

1. 동적 프로그래밍으로 푸는 전형적인 문제로 유명하다. 반드시 외워두는게 좋겠다.
2. 배낭문제(Knapsack) 문제는 이차원배열을 이용에 푸는 것이 일반적이다.
3. 점화식 :
   1. D[i][j] = D[i-1][j] <if> j < W[i]
   2. D[i][j] = max(D[i-1][j]  , D[i-1][j-weight] + value ) j >= W[i]

4. 문제 풀이

본 문제에서 왜 이차원 배열을 사용하는지 이해가 안되었지만 일차원 배열로 구연했을때 같은 i 행에서 이전 dp[j] 가 바뀐 값을 기준으로 추후 나오는 dp[j] 값이 바뀔 수 있기때문에 문제가 생긴다.

예를들면 해당 문제 예시에서 추가적으로 (3,20) 존재한다고 한다면 j 가 3일때 20 으로 업데이트되고 j가 6일때 20이 되야하지만 1차원 배열일 경우 40 이된다. 

1차원 배열을 사용함에도 뒤에서 부터 채워나가면 해당 문제를 해결할 수 있다.

 

<일차원배열>

# 평범한 배낭

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

# 2차원 배열 생성

# j 는 열으로서 각무게를 의미하고
# i 는 행으로서 각각의 물품을 의미한다

# 굳이 2차원 배열로 만든이유
# K 부터 weight-1 까지 역순으로 가야 맞는이유

# -> 앞에서 부터 가게 되면 새롭게 대체된 값에 또 해당 값을 더할 수 있음
# 단적인 예로서 (3,20) 을 생각해보자 dp[3] =20 이 되고 dp[6] = 40 이 되서
# 꼬임

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

for _ in range(N):
    weight , value =  map(int, input().split())
    for j in range(K , weight-1 , -1):
            if weight <= j:
                dp[j] = max(dp[j] , dp[j-weight] + value)

print(dp[K])

<이차원배열>

N , K = map(int, input().split())
for i in range(1,N+1):
    weight , value = map(int, input().split())
    #print(weight)
    for j in range(1,K+1):
        if j < weight : 
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j] , dp[i-1][j-weight] + value)


print(dp[N][K])