[백준] 12865 - 평범한 배낭 (C++)

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

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다니므로 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 100
• 1 ≤ K ≤ 100,000
• 1 ≤ W ≤ 100,000
• 0 ≤ V ≤ 1,000

 

배낭 문제(Knapsack)는 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 물건의 집합이 주어질 때, 배낭에 담은 물건들의 가치의 합이 최대가 되도록 하는 물건들의 부분 집합을 찾는 문제다. 이 문제는 그중에서도 0-1 knapsack으로 물건을 자를 수 없기 때문에 물건의 무게와 가격, 배낭에 남은 용량까지 모두 고려해야 한다.

• 물건을 자를 수 있는 경우는 Fractional knapsack으로 부르며, 물건의 가치를 무게로 나눠 무게 대비 가치가 큰 순서로 물건을 정렬해 넣으면 된다.

 

물건 N개의 정보(W, V)를 입력받으면서 넣을지 말지를 모두 고려해서 푼다면 O(2^N)씩이나 걸리기 때문에 당연히 시간 초과가 발생하게 된다. DP로 풀기 위해 최대 무게가 j인 배낭에 i번째 물건을 넣거나 넣지 않았을 때 얻을 수 있는 누적 가치의 최댓값을 저장할 dp[i][j] 배열을 선언해야 한다.

• i번째 물건을 배낭에 넣으려고 할 때,
  • 배낭의 남은 공간이 물건의 무게보다 크거나 같으면 배낭에 넣을 수 있다.
  • 남은 공간이 물건의 무게보다 작다면 i-1번째 물건까지 가방에 넣은 경우와 가치가 동일하다고 보면 된다.

 

이때, dp 배열이 이전 배열에 영향을 받는 경우는 남은 공간이 물건의 무게보다 작을 때뿐이기 때문에 반복문 조건을 잘 설정하면 2차원 배열이 아닌 1차원 배열만으로도 문제를 해결할 수 있다.

• 1차원 배열을 사용하는 경우엔 i번째 물건 정보를 입력받고, j를 K부터 W까지 역순으로 탐색해야 dp 배열을 중복으로 갱신하는 경우를 막을 수 있다. dp 배열을 갱신할 때, 현재 값(dp[j])과 물건을 넣은 값(dp[j-w])을 비교하기 때문에 역순으로 진행하지 않으면 현재 값이 이미 갱신된 이전 값을 바탕으로 또 갱신될 수 있기 때문이다.

 

2차원 배열을 사용한 경우의 정답 코드는 아래와 같다. 이 경우에도 i번째 dp 배열이 i-1번째 dp 배열에만 영향을 받기 때문에 bool 값을 이용해 메모리를 절약할 수 있다.

#include <iostream>
using namespace std;

int n,k,w,v,dp[2][100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    bool tog;
    for (int i=1; i<=n; i++) {
        cin >> w >> v;
        tog = (i%2==1 ? 1 : 0);
        for (int j=1; j<=k; j++) {
            if (j>=w) dp[tog][j] = max(dp[!tog][j],dp[!tog][j-w]+v);
            else dp[tog][j] = dp[!tog][j];
        }
    }
    cout << dp[tog][k];
}

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, K 입력받기
2. N개의 W, V 입력받으면서 dp 배열 갱신하기
   1. 최대 무게가 K일 때부터 W일 때까지 반복문을 진행하면서 현재 무게에서 i번째 물건의 W를 값에 V를 더한 값과 i번째 물건을 더하지 않은 값을 비교해 최댓값을 저장하기
3. dp[K] 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해 보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1회차

• i번째 dp 배열을 갱신할 때 i-1번째 dp 배열을 이용하지 않도록 구현함

#include <iostream>
#include <algorithm>
using namespace std;

int n,k,w,v,dp[101][100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    for (int i=1; i<=n; i++) {
        cin >> w >> v;
        for (int j=1; j<=k; j++) {
            if (j>=w) dp[i][j] = max({dp[i-1][j],v,dp[i][j-w]+v});
            else dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[n][k];
}

 

---

정답 코드

#include <iostream>
using namespace std;

int n,k,w,v,dp[100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    for (int i=1; i<=n; i++) {
        cin >> w >> v;
        for (int j=k; j>=w; j--) dp[j] = max(dp[j],dp[j-w]+v);
    }
    cout << dp[k];
}