백준 12865 (DP)

12865번: 평범한 배낭

과정

• 처음에는 DP : 자신을 포함하는 물건들의 최대 가치 를 담는 용도였다.

#include <iostream>

#include<vector>

using namespace std;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(nullptr); cout.tie(nullptr);

    int N = 0;  // 물건의 수

    int K = 0;  // 최대 무게

    int W = 0;  // 물건의 무게

    int V = 0;  // 물건의 가치

    int answer = 0;

    vector<pair<int, int>> Things;

    vector<pair<int, int>> DP;  // 자기자신을 포함한 총 무게 K 무게 이하의 물건의 최대 가치

   

    cin >> N >> K;

    DP.resize(N+1, pair<int, int>(0, 0));

    Things.resize(N+1, pair<int, int>(0, 0));

    for (int i = 1; i < N+1; i++)

    {

        cin >> Things[i].first >> Things[i].second;

        DP[i].first = Things[i].first;

        DP[i].second = Things[i].second;

        for(int j = i-1; j > -1; j--)

        {

            // 총 무게가 K 이하

            if (DP[i].first + Things[j].first <= K)

            {

                DP[i].first = DP[i].first + Things[j].first;

                DP[i].second = DP[i].second + Things[j].second;

            }

        }

        answer = max(answer, DP[i].second);

    }

    cout << answer;

    return 0;

}

 

하지만 이 코드의 문제점은 추후에 더 좋은 조건의 물건이 나왔을 때 기존에 있던 물건 중 어떤 물건을 빼야할지 모른다는 점이었다.

 

DP와 Things를 여러가지로 조합해봤지만 결론적으로 DP의 구조와 의미를 무조건 바꿔야했다.

DP[a] = b: a 무게에서 조합할 수 있는 최대 가치 b (밑에 다시 정의함 이거 아님)

 

코드

#include <iostream>

#include<vector>

using namespace std;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(nullptr); cout.tie(nullptr);

    int N = 0;  // 물건의 수

    int K = 0;  // 최대 무게

    int answer = 0;

    vector<pair<int, int>> Things;

    int DP[100001];  // 자기자신을 포함한 총 무게 K 무게 이하의 물건의 최대 가치

   

    cin >> N >> K;

    Things.resize(N+1, pair<int, int>(0, 0));

    for (int i = 1; i < N+1; i++)

    {

        cin >> Things[i].first >> Things[i].second;

    }

    for(int i = 1; i < N+1; i++)  // i : 각각의 물건

    {

        for (int j = K; j > 0; j--) // j : 무게 (최대 무게~ 최소 무게)

        {

            // 최대무게부터 자신의 무게까지 해당되는 DP의 인덱스만 골라서 넣을 거임

            if (Things[i].first <= j)

            {

                // DP[j] : j이하 무게만큼 물건들을 조합해서 최대 가치를 저장

                // 기존 최대 가치 vs 자신의 물건을 포함한 새로운 가치

                DP[j] = max(DP[j], DP[j - Things[i].first] + Things[i].second);

               

                //cout << "i = " << i << ", DP[j] = " << DP[j] << "\n";

            }

            //cout << "\n";

        }

    }

    //for (int i = 0; i < K+2; i++)

    //    cout << DP[i] << "\n";

    cout << DP[K];

    return 0;

}

 

중간에 헷갈렸던게, 

5 14
1 5
2 3
3 6
4 7
5 8

이렇게 입력을 넣으면 무게는 13, 최대 가치는 26이다.

근데 출력은 무게가 K, 즉 14일 때를 출력하고 있다.

 

그림을 보면, 무게가 5일때,

무게 1+3의 가치가 2+3의 가치보다 커서 여기서부터 바뀌기 시작한다.

즉, DP[a] = b: a이하 무게에서 조합할 수 있는 최대 가치 b 라고 이해할 수 있다.