[코드포스 Practice12] D. White Sheet

전에 색종이로 덮는 문제 푼 적 있었는데.. 있었지... 그 때는 색종이 만큼의 배열을 만들어서 덮은 수를 1로 바꿔가며 확인했었는데 이번에는 범위가 너무 커서 그렇게 못했다.

 

그래서 덮는 조건을 확인해가면서 몇 가지 유형으로 나눴다.

 

 

조건은 세 가지로 나눌 수 있다. 

첫번째는 다 덮는거

두번째는 깔끔히 직사각형으로 덮는 거

그 외는 나머지 경우

 

조건은 다음 검은 종이를 얼마만큼 확인해야할지 기준으로 나눴다.

 

첫번째 경우는 다음 검은 종이를 확인할 필요가 없다. 그래서 그냥 NO를 출력하고 종료

그 외 경우는 어쩔 수 없이 다음 종이로 다 덮히는지 판단...

두번째 경우는 다 덮히는 지 확인하는 건 같지만 흰 종이의 범위를 줄일 수 있다. 

 

~~나머지는 집 가서~~

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> x(7);
    vector<int> y(7);

    for (int i = 1; i < 7; i++)
    	scanf("%d %d", &x[i], &y[i]);
    if (x[3] <= x[1] && y[3] <= y[1] && x[2] <= x[4] && y[2] <= y[4])
    {
    	printf("NO");
    	return (0);
    }
    if (y[3] <= y[1] && y[2] <= y[4])
    {
    	if (x[1] < x[4] && x[3] <= x[1] && x[4] < x[2])
    		x[1] = x[4];
    	if (x[3] < x[2] && x[2] <= x[4] && x[1] < x[3])
    		x[2] = x[3];
    }
    else if (x[3] <= x[1] && x[2] <= x[4])
    {
    	if (y[1] < y[3] && y[3] < y[2] && y[2] <= y[4])
    		y[2] = y[3];
    	if (y[1] < y[4] && y[3] <= y[1] && y[4] < y[2])
    		y[1] = y[4];
    }
    if (x[5] <= x[1] && y[5] <= y[1] && x[2] <= x[6] && y[2] <= y[6])
    {
    	printf("NO");
    	return (0);
    }    
    printf("YES");
    return (0);
}

휴 드디어 다풀었다. 

어려운 알고리즘 기법! 이런 문제는 아니었는데 구현이 복잡했다. 

풀면서 이걸 시간 내에 다 풀 수 있을까?? 이런 생각 계속 들었음. 아마 못했을 듯 ~.~

 

 

---

놀라운 걸 배워왔다

 

전에 ㅂㅣAsk휴 (써방임) 과제할 때 얘의 존재에 대해 들었는데 어떻게 사용할지 몰라서 패스했었다. 

암튼.. 이 문제는 좌표압축을 쓰면 빠르고 깔끔하게 풀린다. 

사각형이 3개 밖에 없어서 이 꼭지점 6개를 좌표로 만들고 전의 상자 색칠하는 문제처럼 풀면 바로 풀린다.

신기~~

 

 

lower_bound 기억 안 나서 다시 공부했다

https://burningjeong.tistory.com/123

lower_bound, upper_bound

이런 애였지

 

아 여기 lower_bound 대신에 find를 써도 되지 않을까 궁금했는데 find는 O(N)이 걸리고 lower_bound()는 이분탐색으로 찾아서 O(logN)이 걸린다. 알아둬야지 ^~^

 

 

신기하구만..

신기해..

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Mapping
{
public :
    void init(const vector<int>& raw, int base = 0)
    {
        start = base;
        arr = raw;
        sort(arr.begin(), arr.end());
        arr.erase(unique(arr.begin(), arr.end()), arr.end());
    }

    int get_idx(int k)
    {
        return start + (lower_bound(arr.begin(), arr.end(), k) - arr.begin());
    }

    int get_value(int idx)
    {
        return arr[idx - start];
    }

    int size()
    {
        return arr.size();
    }

private:
    int start;
    vector<int> arr;
};

int color[6][6];

int main()
{
    vector<int> x(6), y(6);

    for (int i = 0; i < 6; i++)
        scanf("%d %d", &x[i], &y[i]);

    Mapping xmap, ymap;
    xmap.init(x);
    ymap.init(y);

    for (int i = 0; i < 6; i++)
    {
        x[i] = xmap.get_idx(x[i]);
        y[i] = ymap.get_idx(y[i]);
    }

    for (int i = 2; i < 6; i += 2)
        for (int sx = x[i]; sx < x[i + 1]; sx++)
            for (int sy = y[i]; sy < y[i + 1]; sy++)
                color[sx][sy] = 1;

    for (int sx = x[0]; sx < x[1]; sx++)
    {
        for (int sy = y[0]; sy < y[1]; sy++)
        {
            if (color[sx][sy] == 0)
            {
                printf("YES");
                return 0;
            }
        }
    }
    printf("NO");
    return (0);
}

 

 

코드는 이렇다