[BOJ] 백준 2643 색종이 올려 놓기 (KOI 1999 초등부)

문제 링크

www.acmicpc.net/problem/2643

2643번: 색종이 올려 놓기

 

풀이

1) 색종이의 두 변 중 작은 변이 항상 앞으로 오도록 저장하고, 오름차순 정렬해줍니다.

2) 배열 $d$를 정의합시다. $d[i]$는 $i$번째 색종이보다 작거나 같은 색종이들을 $i$번째 색종이 위에 최대로 쌓을 수 있는 개수입니다.

3) 가장 긴 증가하는 부분 수열 (LIS) 문제와 같은 방식으로 $d[i]$를 갱신할 수 있습니다.

4) 모든 $d[i]$ 중 가장 큰 값을 정답으로 출력합니다.

 

정답 코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;

int n;
int d[111];
vector<pii> p;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        p.emplace_back(min(x, y), max(x, y));
    }
    sort(all(p));
    int ans = 1;
    for (int i = 0; i < n; i++) {
        d[i] = 1;
        auto[x, y] = p[i];
        for (int j = 0; j < i; j++) {
            auto[nx, ny] = p[j];
            if (x >= nx && y >= ny) {
                d[i] = max(d[i], d[j] + 1);
            }
        }
        ans = max(ans, d[i]);
    }
    cout << ans;
}