풀이
요약: 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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이