6. dp : LIS, Knapsack

6.md

0.01MB

오늘도 dp.

1. 가장 긴 증가하는 부분 순열 Longest Incresing Subsequence

11053번 문제를 보면서 생각해보자.

dp[i] : i번째 원소가 마지막인 가장 긴 증가하는 부분 수열

예를 들어 10, 20, 10, 30, ... 이렇게 있을 때

dp[1] = 1

dp[2] = 2

dp[3] = 1

dp[4] = 3

...

dp[i] = max(dp[j]) + 1
(if arr[j] < arr[i], for all j < i )

즉, dp[i] = i보다 앞에있는 원소들 중에 arr[i]보다 작은 원소 중 가장 큰거 + 1

#include <iostream>
using namespace std;
int dp[1000];
int arr[1000];
int main(){
    int N; cin >> N;
    for(int i=0; i<N; ++i){
        cin >> arr[i];
    }

    int res=-1;

    for(int i=0; i<N; ++i){
        dp[i] = 1; // 기본값 설정

        for(int j=0; j<i; ++j){
            if(arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        res = max(res, dp[i]);
    }
    cout << res << '\n';
}

 

참고 문제 : boj.kr/11053, boj.kr/11722, boj.kr/2565, boj.kr/1965, boj.kr/2631, boj.kr2643, boj.kr/11054

2. 냅색(knapsack) : 베낭문제

12865번을 보며 생각해보자.

W[i] : i번째 물건의 무게weight

V[i] : i번째 물건의 가치value

dp[i][w] : 1번째 물건 ~ i번째 물건까지 고려 했고, 가방 용량을 w만큼 채웠을 때의 최대 가치 로 정의한다.

dp[i][w] = max(dp[i-1][w-W[i]] + V[i], dp[i-1][w]); for all w

이를 0/1 knapsack이라고 한다. : 물건을 쪼개서 넣을 수 없을 때 사용한다.

1번째 물건 => 무게 : 3, 가치 : 4
2번째 물건 => 무게 : 2, 가치 : 2

두 물건이 있을 때

dp[1][0] = 0
dp[1][1] = 0
dp[1][2] = 0
dp[1][3] = 4
dp[1][4] = 4 = dp[0][4] + V[1] // 가방의 공간 1만큼을 낭비하고 1번째 물건을 올려놓은거.
...
dp[N][K] = 답.

참고 문제 : boj.kr/12865, boj.kr/2294, boj.kr/9084

99. 부록 : 참고 문제 풀이

• boj.kr/11053

#include <iostream>
using namespace std;
int dp[1000];
int arr[1000];
int main(){
    int N; cin >> N;
    for(int i=0; i<N; ++i){
        cin >> arr[i];
    }

    int res=-1;

    for(int i=0; i<N; ++i){
        dp[i] = 1; // 기본값 설정

        for(int j=0; j<i; ++j){
            if(arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        res = max(res, dp[i]);
    }
    cout << res << '\n';
}

• boj.kr/11722

#include <iostream>
using namespace std;
int dp[1001];
int arr[1001];
int main(){
    int N; cin >> N;
    for(int i=1; i<=N; ++i){
        cin >> arr[i];
    }

    int res=0;

    for(int i=1; i<=N; ++i){
        dp[i]=1;
        for(int j=1; j<i; ++j){
            if(arr[i]<arr[j]) dp[i]=max(dp[i], dp[j]+1);
        }
        res = max(res, dp[i]);
    }
    cout << res << '\n';
}

• boj.kr/2565

#include <iostream>
using namespace std;
int A[502], B[502], dp[501];
int main(){
    int N;  cin >> N;
    for(int i=1; i<=N; ++i){
        int a, b;
        cin >> a >> b;
        A[a]=b;
        B[b]=a;
    }
    int res=0;
    for(int i=1; i<=500; ++i){
        if(A[i]==0) continue;
        dp[i]=1;
        for(int j=1; j<i; ++j){
            if(A[j]<A[i]) dp[i]=max(dp[i], dp[j]+1);
        }
        res = max(res, dp[i]);
    }
    cout << N-res << '\n';
}

• boj.kr/1965

#include <iostream>
using namespace std;
int dp[1001];
int arr[1001];
int main(){
    int N; cin >> N;
    for(int i=0; i<N; ++i){
        cin >> arr[i];
    }

    int res=-1;

    for(int i=0; i<N; ++i){
        dp[i] = 1; // 기본값 설정

        for(int j=0; j<i; ++j){
            if(arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        res = max(res, dp[i]);
    }
    cout << res << '\n';
}

• boj.kr/2631

#include <iostream>
using namespace std;
int dp[1001];
int arr[1001];
int main(){
    int N; cin >> N;
    for(int i=0; i<N; ++i){
        cin >> arr[i];
    }

    int res=-1;

    for(int i=0; i<N; ++i){
        dp[i] = 1; // 기본값 설정

        for(int j=0; j<i; ++j){
            if(arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        res = max(res, dp[i]);
    }
    cout << N-res << '\n';
}

• boj.kr2643

#include <iostream>
#include <algorithm>
using namespace std;
pair<int, int> arr[101];
int dp[101];
bool comp(pair<int, int> a, pair<int, int> b){
    if(a.first==b.first) return a.second>b.second;
    return a.first > b.first;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N; cin >> N;
    for(int i=1; i<=N; ++i){
        int a, b;
        cin >> a >> b;
        arr[i].first = max(a,b);
        arr[i].second = min(a, b);
    }
    sort(arr+1, arr+N+1, comp);

    int res=0;
    for(int i=1; i<=N; ++i){
        dp[i]=1;
        for(int j=1; j<i; ++j){
            if(arr[i].first<=arr[j].first && arr[i].second <= arr[j].second) dp[i]=max(dp[i], dp[j]+1);
        }
        res = max(res, dp[i]);
    }
    cout << res << '\n';
}

• boj.kr/11054

#include <iostream>
using namespace std;
int dp1[1001]; // left to right
int dp2[1001]; // right to left
int arr[1001];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N; cin >> N;
    for(int i=1; i<=N; ++i){
        cin >> arr[i];
    }
    for(int i=1; i<=N; ++i){
        dp1[i]=1;
        for(int j=1; j<i; ++j){
            if(arr[j]<arr[i]) dp1[i] = max(dp1[i], dp1[j]+1);
        }
    }
    for(int i=N; i>=1; --i){
        dp2[i]=1;
        for(int j=N; j>i; --j){
            if(arr[j]<arr[i]) dp2[i] = max(dp2[i], dp2[j]+1);
        }
    }
    int res=0;
    for(int i=1; i<=N; ++i){
        res=max(res, dp1[i]+dp2[i]-1);
    }
    cout << res << '\n';
}

• boj.kr/12865

#include <iostream>
using namespace std;
int dp[101][100001];
int W[101];
int V[101];

int main(){
    int N, K; cin >> N >> K;
    for(int i=1; i<=N; ++i){
        cin >> W[i] >> V[i];
    }

    for(int i=1; i<=N; ++i){
        for(int w=0; w<W[i]; ++w){
            dp[i][w] = dp[i-1][w];
        }
        for(int w=W[i]; w<=K; ++w){
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i]] + V[i]);
        }
    }

    cout << dp[N][K] << '\n';
}

• boj.kr/2294

#include <iostream>
#define MN 100000
#define INF 987654321
typedef long long int ll;
using namespace std;
ll V[101];
ll dp[101][MN+1];
//dp[i][j] = i번째 동전까지 고려했을 때, j의 가치를 가진 동전의 개수

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, k;   cin >> n >> k;
    for(int i=1; i<=n; ++i){
        cin >> V[i];
    }
    for(int i=0; i<=n; ++i){
        for(int j=1; j<=k; ++j){
            dp[i][j] = INF;
        }
    }


    for(int i=1; i<=n; ++i){
        for(int j=1; j<V[i]; ++j){
            dp[i][j] = dp[i-1][j];
        }
        for(int j=V[i]; j<=k; ++j){
            dp[i][j] = min(dp[i-1][j], min(dp[i-1][j-V[i]] + 1, dp[i][j-V[i]] + 1));
        }
    }

    if(dp[n][k] == INF) cout << "-1" << '\n';
    else cout << dp[n][k] << '\n';


}

• boj.kr/9084

#include <iostream>
using namespace std;
int main(){
    int T; cin >> T;
    while(T--){
        int V[21] = {};

        int N; cin >> N;
        for(int i=1; i<=N; ++i){
            cin >> V[i];
        }
        int M; cin >> M;

        int dp[21][10001] = {};
        //dp[i][j] = i번째 동전까지 봤을 때, 
        //           j의 가치를 만드는 방법의 수
        for(int i=1; i<=N; ++i){
            dp[i][V[i]] = dp[i-1][V[i]] + 1; 
            for(int j=1; j<V[i]; ++j){
                dp[i][j] = dp[i-1][j];
            }
            for(int j=V[i]+1; j<=M; ++j){
                dp[i][j] = dp[i-1][j] + dp[i][j-V[i]];
            }
        }
        cout << dp[N][M] << '\n';

    }
}