8103 : Rooks

풀이

요약: n*n의 체스판에 n개의 룩을 배치해야 하는데, 어떤 룩도 서로를 잡을 수 없도록 배치해야한다. 그런데 그냥 배치하는 건 아니고, 각각의 룩을 배치할 수 있는 어떤 직사각형의 영역이 n개 주어진다. 각각의 룩은 각각의 영역 내에만 배치될 수 있다.

룩은 가로/세로로만 움직일 수 있다는 사실을 조금 관찰해보면, 답을 구하는 데 있어 가로 좌표와 세로 좌표가 독립적임을 알 수 있다.

즉, 한 축(가로 또는 세로)에 대해 조건에 맞게 배치하는 일을 두 번 해주고, 나중에 답을 합쳐줘도 된다는 뜻이다.

체스판의 크기가 3000정도 되므로, 이걸 다 돌면서 i번째 칸에는 몇 번째 룩을 배치할지를 결정할 것이다.

아무 룩이나 집어넣는 건 아니고,

i를 구간 내에 포함하는 [s, e]들의 집합 S를 가정할 때, S의 원소들 중 가장 e가 작은 원소를 선택할 것이다.

꽤 well known스러운데, 아무튼 이러면 답을 구할 수 있다.

증명은 회의실배정(icpc.me/1931) 문제랑 비슷하게 exchange argument였나? 그걸로 되는 모양이다. (사실 그냥 될 거 같아서 짜고 증명은 안 해봤다 ㅎ)

코드

#include <cstdio>
#include <algorithm>
using namespace std;

int n, cx[3003], cy[3003];
struct abc {
    int s, e, idx;
    bool operator <(abc a)const {
        if (e == a.e) return s < a.s;
        return e < a.e;
    }
} x[3003], y[3003], r[3003];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d %d", &x[i].s, &y[i].s, &x[i].e, &y[i].e);
        x[i].idx = y[i].idx = i;
    }
    sort(x+1, x+n+1); sort(y+1, y+n+1);
    for (int i = 1; i <= n; i++) {
        int f = 0;
        for (int j = 1; j <= n; j++) {
            if (!cx[j] && x[j].s <= i && i <= x[j].e) {
                cx[j] = r[x[j].idx].s = j;
                f++;
                break;
            }
        }
        for (int j = 1; j <= n; j++) {
            if (!cy[j] && y[j].s <= i && i <= y[j].e) {
                cy[j] = r[y[j].idx].e = j;
                f++;
                break;
            }
        }
        if (f != 2) {
            return !puts("NIE");
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%d %d\n", r[i].s, r[i].e);
    }
    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-28 10:30

Read more posts by this author