[2643번] 색종이 올려 놓기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Sort

2. Lis Algorithm

http://www.crocus.co.kr/429  다음 링크를 통해 lis 알고리즘의 다른 문제를 확인해 볼 수 있다.

위의 링크에는 lis에 대해 조금 더 설명을 해 두었다.

이 코드는

입력을 받을 때 부터, x보다 y가 길이가 더 길면 즉, 가로보다 세로가 길면 종이를 돌린다 생각하여

가로가 무조건 더 길게 되도록 하여 값을 저장시킨다.

그리고 가로 크기 순서대로 오름차순 정렬을 한 후,

가로에 의해 정렬된 세로만을 확인하여 lis 알고리즘을 이용하면 정답을 도출해 낼 수 있다.

lis알고리즘은 부분 증가 수열에서 유용하다.  

소스 코드 : 

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
struct point {
    int x, y;
};
 
point p[100000];
int lis[100001];
int arr[100001];
 
bool comp(point const& a, point const& b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
 
int _lower_bound(int start, int end, int *arr, int target)
{
    int mid;
    while (end - start > 0)  // 주어진 범위[start,end]에서 탐색하도록 한다. start == end이면 반복 종료
    {
        mid = (start + end) / 2;  // 주어진 범위의 중간 위치를 계산한다
 
        if (arr[mid] <= target) // 찾고자 하는 값보다 작으면 오른쪽으로 한 칸만 더 시작 구간 갱신
            start = mid + 1;
 
        else  // 찾고자 하는 값보다 크면 거기까지 끝 구간 갱신
            end = mid;
    }
    return end + 1; // 찾는 구간에 없는 경우 가장 마지막 +1 위치 전달
}
 
 
int main()
{
    int i, n, x, y,j=0;
 
    scanf("%d", &n);
 
    for (i = 0; i<n; ++i) {
        scanf("%d%d", &x, &y);
 
        if (y > x)
            p[i] = { y,x };
        else
            p[i] = { x, y };
    }
 
    sort(p, p + n, comp);
 
    for (int t = 0; t < n; t++)
        arr[t] = p[t].y;
 
    int cnt = 0;
 
    i = 0;
 
    lis[i] = arr[i];
    i++;
 
    while (i < n)
    {
        // lis의 가장 큰 값보다 더 큰값이 들어오면
        if (lis[j] <= arr[i])
        {
            lis[j + 1] = arr[i];
            j++;
        }
 
        else
        {
            int ans = _lower_bound(0, j, lis, arr[i]);
            lis[ans - 1] = arr[i];
        }
 
        i++;
    }
 
    printf("%d", j+1);
 
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>