[백준 12865] 평범한 배낭

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

12865번: 평범한 배낭

[백준 12865] 평범한 배낭 문제입니다.

최근에 어느 쇼핑몰의 코딩테스트를 봤습니다.

코딩테스트 당시 문제가 완전탐색을 돌기에는 시간복잡도가 2^100이라 효율성 면에서 좋지못해서 DP임을 확신했습니다.

하지만 점화식이 떠오르지 않아 반례가 있을것 같았지만 Greedy 알고리즘을 썼습니다.

 

시험 후 얘기를 들어보니 해당 문제는 01 KnapSack이라는 얘기를 들었고 DP를 자유롭게 쓸 수 있을정도로 공부할 필요성을 느꼈습니다.

 

그런 의미에서 이번 문제는 01 KnapSack입니다.

이름은 다르지만 해당 문제는 그 유명한 01 KnapSack과 완전히 동일한 문제입니다.

 

먼저 가시적으로 확인하기 위해 표를 먼저 보여드리겠습니다.

물건 갯수4 배낭 무게6

물건1: 무게2 가치2

물건2: 무게1 가치3

물건3: 무게2 가치1

물건4: 무게3 가치2

	배낭 무게:0	배낭 무게:1	배낭 무게:2	배낭 무게:3	배낭 무게:4	배낭 무게:5	배낭 무게:6
1번째 물건	0	0	2	2	2	2	2
2번째 물건	0	3	3	5	5	5	5
3번째 물건	0	3	3	5	5	6	6
4번째 물건	0	3	3	5	5	6	7

방법입니다.

먼저 (물건 갯수 * 최대 배낭 무게)의 크기를 가진 2차원 배열을 선언합니다.(저는 이름을 DP[][]로 선언했습니다.)

이 배열에는 가치가 들어갈 겁니다.

 

외부 반복문에서 물건은 1번째 물건부터 차례(i)대로 진행합니다.

그리고 내부 반복문에서 배낭 무게가 0이라고 전제할때부터 시작하며 실제 배낭 무게(j)까지 진행합니다.

 

반복문의 내부에서 DP가 시작됩니다.

 

현재 배낭 무게가 해당 차례의 물건을 담지 못하는 무게이면 전번 차례의 물건일때의 가치를 넣어줍니다.

1번째 물건일 경우는 전번 차례 물건이 없으니 0이 들어갑니다.

 

현재 배낭 무게가 해당 차례의 물건을 담을 수 있는 경우입니다.

이 때 나올 수 있는 경우는 2가지 입니다.

1. 해당 차례의 물건을 담는 경우
2. 해당 차례의 물건을 담지 않는 경우

1번은 해당 차례의 물건을 담아야합니다.

그러니 (해당 배낭무게-해당차례 물건의 무게)의 배낭에 해당 차례 물건의 가치를 더해야합니다.

그러므로 DP[i][j]=DP[i][j-해당차례 물건 무게]+해당차례 물건 가치 입니다.

 

2번은 담지 않는 경우이므로 전번 물건을 담았을때 해당 배낭 무게의 최대값인 DP[i][j]=DP[i-1][j]입니다.

 

이 1번과 2번중 값어치가 높은 배낭이 저희가 원하는 배낭입니다.

그러므로 DP[i][j]=max((DP[i][j-해당차례 물건 무게]+해당차례 물건 가치),DP[i-1][j])입니다.

 

이런식으로 반복문을 마지막까지 진행하면 DP[물건의 갯수][최대 배낭 무게]에 최대 가치가 들어가게 됩니다.

 

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int N,K,item[102][2],dp[102][100'003];

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> N >> K;
    for(int i=1;i<=N;i++)
    {
        cin >> item[i][0] >> item[i][1];
    }

    for(int i=1;i<=N;i++)
    {
        int weight = item[i][0], val=item[i][1];
        for(int j=0;j<=K;j++)
        {
            if(j<item[i][0]) dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight]+val);
        }
    }
    
    cout << dp[N][K];
}

DP는 코드는 정말 간단하지만 생각하기는 정말 어렵습니다.

점화식을 직접 생각하지 못하는 저같은 사람에게

DP를 정복하는 방법은 나와있는 모든 DP 문제를 풀고 모든 유형을 익히는 것이라 생각합니다.