[Algorithm]Baekjoon 2643번 :: 색종이 올려 놓기

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
struct Node
{
    int width;
    int height;
};
 
bool cmp(const Node& a, const Node& b)
{
    if (a.width == b.width)
    {
        return a.height < b.height;
    }
 
    return a.width < b.width;
}
 
int n;
vector<Node> nodes;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    nodes.resize(n);
    
    for (int i = 0; i < n; ++i)
    {
        cin >> nodes[i].width >> nodes[i].height;
 
        if (nodes[i].height > nodes[i].width)
        {
            int temp = nodes[i].height;
            nodes[i].height = nodes[i].width;
            nodes[i].width = temp;
        }
    }
 
    sort(nodes.begin(), nodes.end(), cmp);
 
    vector<int> lis;
 
    for (int i = 0; i < nodes.size(); ++i)
    {
        int num = nodes[i].height;
        int index = upper_bound(lis.begin(), lis.end(), num) - lis.begin();
 
        if (index == lis.size())
        {
            lis.push_back(num);
        }
        else
        {
            lis[index] = num;
        }
    }
 
    cout << lis.size();
}
 
 
 

 

 

보자마자 정렬 후 lis길이 구하는 문제인것을 알 수 있었다.

색종이를 점점 작은크기로 올려놓을 때, 최대개수를 구하는 문제인데 올려놓기위해서는 아래색종이보다 더 작아야한다.

즉, 문제조건에 의하면 아래색종이랑 크기가 같거나, 더 작아야 한다.

그리고 더 중요한 조건이 하나있는데, 색종이는 회전이 가능하다는 것.

 

어쨌든 색종이를 쌓기위해선 아래색종이에 포함되어져야 한다.

그렇기 때문에 일단 한변의 길이를 기준으로 오름차순정렬을 해준다음, 나머지 변으로 LIS길이를 출력해주면 된다.

쌓는다는 개념을 적용하려면 내림차순해서 내림차순길이를 구하는게 맞는데, 오름차순이 편해서 그냥 위에서부터 아래로 쌓는다 생각하고 풀었다.

 

그리고 색종이는 회전이가능하기 때문에, 처음에 정보를 입력받을 때 일관되게 입력받아야 한다.

즉, 만약 본인이 width를 기준으로 오름차순 정렬 후, height로 lis길이를 구하고싶다면,

처음에 입력받을 때 무조건 width값을 더 크게 받아야 한다. width랑 height를 입력받았을 때 width가 더 작다면 스왑해준다. 색종이는 회전시키는게 가능하기때문이다.