step 1
step 2
더보기
더보기
$N$ * $N$ 크기에 $N$개의 탱크를 놓습니다. 어떤 행이나 열에도 2개 이상의 탱크가 놓일 수 없으니 결국 모든 행에 1대, 모든 열에 1대의 탱크가 놓입니다.
열을 먼저 생각해 봅시다. 처음에 탱크가 배치되어 있고 이 탱크들을 모든 열에 1대씩 있도록 재배치해야 합니다.처음 배치에서 두 탱크를 고른다고 생각해 봅시다. 왼쪽에 있는 탱크를 $X$, 오른쪽에 있는 탱크를 $Y$라고 합시다. 이 두 탱크는 재배치된 이후에도 $X$가 $Y$ 왼쪽에 있어야 합니다. 이것을 잘 생각해 보면 열을 기준으로 정렬한 뒤 제일 왼쪽에 있는 탱크는 1번째 열, 두번째로 왼쪽에 있는 탱크는 2번째 열, ..., $N$번째로 왼쪽에 있는 탱크는 $N$번째 열에 있어야 함을 알 수 있습니다. 행도 마찬가지로 하면 됩니다.
코드
더보기
더보기
#include<stdio.h>
#include<algorithm>
using namespace std;
struct data {
int x, y;
inline bool operator<(const data &temp)const {
return x < temp.x;
}
}b1[1000],b2[1000];
int main() {
int n, j,i,x,y;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%d %d", &x, &y);
b1[i].x = x;
b1[i].y = i;
b2[i].x = y;
b2[i].y = i;
}
sort(b1 + 1, b1 + n + 1);
sort(b2 + 1, b2 + n + 1);
int cnt = 0;
for (i = 1; i <= n; i++) {
if (b1[i].x > i) {
for (j = i; j <= b1[i].x - 1; j++) cnt++;
}
if (b1[i].x < i) {
for (j = b1[i].x; j <= i - 1; j++) cnt++;
}
}
for (i = 1; i <= n; i++) {
if (b2[i].x > i) {
for (j = i; j <= b2[i].x - 1; j++) cnt++;
}
if (b2[i].x < i) {
for (j = b2[i].x; j <= i - 1; j++) cnt++;
}
}
printf("%d\n", cnt);
for (i = 1; i <= n; i++) {
if (b1[i].x > i) {
for (j = i; j <= b1[i].x-1; j++) printf("%d U\n", b1[i].y);
}
}
for (i = n; i >= 1; i--) {
if (b1[i].x < i) {
for (j = b1[i].x; j <= i - 1; j++) printf("%d D\n", b1[i].y);
}
}
for (i = 1; i <= n; i++) {
if (b2[i].x > i) {
for (j = i; j <= b2[i].x-1; j++) printf("%d L\n", b2[i].y);
}
}
for (i = n; i >= 1; i--) {
if (b2[i].x < i) {
for (j = b2[i].x; j <= i - 1; j++) printf("%d R\n", b2[i].y);
}
}
return 0;
}
'PS - 알고리즘' 카테고리의 다른 글
17398 - 통신망 분할 (0) | 2024.06.13 |
---|---|
13209 - 검역소 (0) | 2024.06.02 |
11873 - 최대 직사각형 (0) | 2024.05.26 |
13537 - 수열과 쿼리 1 (0) | 2024.05.26 |
1055 - 끝이없음 (0) | 2024.05.26 |