[BOJ/백준][Gold4] 2643 : 색종이 올려 놓기 (C++)

www.acmicpc.net/problem/2643  

2643번: 색종이 올려 놓기

 

[난이도] Gold4

[유형] DP

 

[풀이]

2차원 LIS 문제이다.

정렬 이후 DP로 해결할 수 있다.

 

점화식 :

dp[n] = max(dp[i]); (n+1 <= i <= N)

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct P{
    int u,v;
};
int N,dp[101];
P a[101];
bool cmp(P& a,P& b){
    if(a.u > b.u) return 1;
    else if(a.u==b.u) return a.v > b.v;
    return 0;
}
int sol(int n){
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret = 0;
    for(int i=n+1;i<=N;i++) if(a[i].v <= a[n].v) ret = max(ret,sol(i));
    return ret += 1;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u<v) swap(u,v);
        a[i].u=u, a[i].v=v;
    }
    a[0].u=a[0].v=9e8;
    sort(a,a+N+1,cmp);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0)-1);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2643.cpp