[BAE/<JOON> 문제풀이] 2643. 색종이 올려놓기

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

2643번: 색종이 올려 놓기

 

핵심::

색종이 정렬

 

풀이::

색종이를 큰 변의 크기 위주로 정렬하고 각 단계에서 윗쪽의 색종이들 중 몇개를 올려놓을 수 있는지 검사한다.

 

이 때 같은 색종이를 여러번 세게 되므로

(a -> b -> c 순서로 먹힌다면 a -> b 에서 a 한번 (a, b) -> c에서 한번)

 

 이 부분을 중복계산하지 않도록 코딩하면 된다. 

 

DP 배열에 해당 번호의 색종이 위에 올려놓을 수 있는 개수를 저장해놓고 중복 계산을 방지한다.

 

사설::

문제 자체는 쉬운 기초 DP지만 자꾸 Sort 함수 돌릴 때 Invalid Comparer? 라는 에러가 자꾸 뜬다.

 

DP에 전달하는 비교 함수에는 등호가 들어갈 수 없단다. 이 문제 때문에 불대수 복잡하게 짜다가 때려 치우고

 

그냥 직접 정렬했다.

 

다른거 풀다가 시간 빵꾸날 것 같아서 쉬워보이는 거 잡았는데 이게 시간 더 오래 걸렸다.

 

코드::

// 2643.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct pp {
    int x, y;
};

//a가 b보다 작다
bool cmp(pp a, pp b) {    
    if (a.x == b.x) {
        return a.y >= b.y;
    }
    else return a.x >= b.x;
}

bool cmp2(pp a, pp b) {
    return a.x >= b.x && a.y >= b.y;
}

int main()
{
    int n; cin >> n;
    vector<pp> arr(n + 1);
    for (int i = 1; i <= n; i++) {
        int x, y; cin >> x >> y;
        arr[i].x = x > y ? x : y; arr[i].y = x < y ? x : y;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (cmp(arr[i], arr[j])) {
                auto t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
    }

    /*for (int i = 1; i <= n / 2; i++) {
        auto t = arr[i];
        arr[i] = arr[n - i + 1];
        arr[n - i + 1] = t;
    }*/

    vector<int> dp(n + 1, 1);    
    int dmx = -1;
    for (int i = 2; i <= n; i++) {
        int mx = 0;
        for (int j = 1; j < i; j++) {
            if (cmp2(arr[i], arr[j])) { //i가 j보다 크거나 같다
                mx = mx > dp[j] ? mx : dp[j];
            }
        }
        dp[i] += mx;
        dmx = dp[i] > dmx ? dp[i] : dmx;
    }
    
    cout << dmx;

    return 0;
}