백준 BOJ 2643 - 색종이 올려 놓기

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

2643번: 색종이 올려 놓기

DP 문제.

 

DP[i] 를 i번 색종이를 제일 위에 쌓을때 최대 장수로 정의한다.

dp[i]를 구하는 방법은 i번 색종이 밑에 놓일 수 있는 보다 큰 색종이 k에 대한

dp[k] 와 비교를 해서,

dp[i] = max(dp[i], dp[k]+1) 식으로 계산해주면 된다.

 

이때, k를 보다 빨리 찾고 편하게 비교하기 위해서,

입력으로 받는 색종이를 일괄적으로 가로 / 세로로 방향을 고정해준 다음에

색종이들을 변 길이를 기준으로 정렬해주면 보다 비교하기 편하게 된다.

 

시간복잡도는 O(N^2)

dp[i]의 초기 값은 자기 자신만이 쌓아져있는 1임에 유의하자.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

int dp[123] = {0};
vector<pair<int,int>> v;

int main(){
	int N,a,b;
	int ans = 0;
	
	cin >> N;
	for(int i=1; i<=N; i++){
		cin >> a >> b;
		v.push_back({max(a,b),min(a,b)});
	}
	
	sort(v.begin(), v.end(), greater<pair<int,int>>());
	
	for(int i=0; i<N; i++){
		dp[i] = 1;
		for(int j=0; j<i; j++){
			if(v[j].x >= v[i].x && v[j].y >= v[i].y){
				dp[i] = max(dp[i], dp[j]+1);
				ans = max(ans, dp[i]);
			}
		} 
	}
	cout << ans;
	return 0;
}