[백준][Python] 12865 평범한 배낭

# 문제 링크

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

 

# 문제

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

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

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

 

# 입력

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

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

 

# 출력

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

 

# 예제

예제입력	예제출력
4 7 6 13 4 8 3 6 5 12	14

 

---

# 문제 풀이

https://github.com/taerimiiii/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/12865.%E2%80%85%ED%8F%89%EB%B2%94%ED%95%9C%E2%80%85%EB%B0%B0%EB%82%AD

Algorithm/백준/Gold/12865. 평범한 배낭 at main · taerimiiii/Algorithm

 

dp문제이다. 처음에 읽고 정렬이 필요..한가..? 싶었다. 작은 것 부터 배낭에 집어넣어야 할 것 같았지만,, 사실 dp문제에서 정렬을 요구하는 경우는 별로 없는 것 같다. 애초에 최대/최소를 구하기 위한? 방법이기 때문에 정렬이 들어가는게 이상하달까 음음...

정석대로 리스트를 정방향으로 순회하며 dp를 갱신하려 하면 무조건 2차원 배열이 필요하다. 이걸 몰라서 한참 헤맸다.

 

2차원 dp풀이

import sys
input = sys.stdin.readline

# 2차원 dp 풀이

n, k = map(int, input().split())
weight = [0] * (n+1)
value = [0] * (n+1)
for i in range(1, n+1) :
    weight[i], value[i] = map(int, input().split())

dp = [[0] * (k+1) for _ in range(n+1)]  # 행: 물건의 갯수 (0 ~ n) / 열: 가방의 최대용량(0 ~ k)
for target in range(1, n+1) :           # target: 모든 물건을 순차적으로 탐색
    for idx in range(1, k+1) :          # idx: 가방의 최대용량을 1부터 k까지 증가
        if idx >= weight[target] :      # 물건을 가방에 넣을 수 있다면
            dp[target][idx] = max(dp[target-1][idx], # 이전 물건까지 넣은 케이스와, 이전 물건에서 지금 물건을 넣을 무게만큼
                                  dp[target-1][idx-weight[target]] + value[target]) # 딱 뺀 경우에 지금 물건을 더한 것 중 큰걸 저장.
        else:                           # 물건을 가방에 넣지 못한다면
            dp[target][idx] = dp[target-1][idx]   # 이전 물건까지 넣은 케이스를 받는다. (이전 물건까지 넣은 케이스가 최대이므로)

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

 

이전 행이 이전 물건까지 배낭에 최대치로 넣을 수 있는 케이스이다. 즉, 이번 행에서는 이전 행의 값을 받으면서 갱신해 주면 된다.

또 다른 중요한 부분은 물건을 넣기 위해 필요한 무게 공간을 확보하기 위한 인덱스 뺄셈 연산이다.

 

 

1차원 dp풀이

import sys
input = sys.stdin.readline

# 1차원 dp 풀이

n, k = map(int, input().split())
weight = [0] * (n+1)
value = [0] * (n+1)
for i in range(1, n+1) :
    weight[i], value[i] = map(int, input().split())

dp = [0] * (k+1)                    # 가방의 최대용량(0 ~ k)
for target in range(1, n+1) :       # target: 모든 물건을 순차적으로 탐색
    for idx in range(k, 0, -1) :    # idx: 가방의 최대용량을 k부터 1까지 역으로 탐색
        if idx >= weight[target] :  # 물건을 가방에 넣을 수 있다면
            dp[idx] = max(dp[idx],  # 원래 가방에 넣을 수 있던 값과, 물건의 무게만큼 뺀 경우 dp 값에 지금 넣을 물건 값을
                          dp[idx-weight[target]] + value[target]) # 더한 것 중 큰걸 저장

print(dp[-1])

# 정방향으로 탐색하면, 뒤로 가면서 앞에 weight[target]만큼 떨어진 값을 더해야 하는데,
# 이미 앞에서 갱신되었으므로 잘못된 값을 참조하게 된다.
# 그냥 dp일 삘인데 앞에서 계산이 안 되면 뒤에서 계산하는걸로 생각하면 됨.

 

dp 리스트를 역방향으로 탐색하면 1차원 dp로도 풀이 가능하다. 장점은 메모리를 아낄 수 있다.