1022 - 소용돌이 예쁘게 출력하기
본문
크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다.
이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그리고 나서 0행 1열에 숫자 2를 쓴다. 거기서 부터 소용돌이는 반시계 방향으로 시작된다. 다음 숫자는 다음과 같이 채우면 된다.
1
2
3
4
5
6
7
8
9
-3 -2 -1 0 1 2 3
--------------------
-3 |37 36 35 34 33 32 31
-2 |38 17 16 15 14 13 30
-1 |39 18 5 4 3 12 29
0 |40 19 6 1 2 11 28
1 |41 20 7 8 9 10 27
2 |42 21 22 23 24 25 26
3 |43 44 45 46 47 48 49
이 문제는 위와 같이 채운 것을 예쁘게 출력하면 된다. $r_1, c_1, r_2, c_2$가 입력으로 주어진다. $r_1, c_1$은 가장 왼쪽 위 칸이고, $r_2, c_2$는 가장 오른쪽 아래 칸이다.
예쁘게 출력한다는 것은 다음과 같이 출력하는 것이다.
- 출력은 $r_1$행부터 $r_2$행까지 차례대로 출력한다.
- 각 원소는 공백으로 구분한다.
- 모든 행은 같은 길이를 가져야 한다.
- 공백의 길이는 최소로 해야 한다.
- 모든 숫자의 길이(앞에 붙는 공백을 포함)는 같아야 한다.
- 만약 수의 길이가 가장 길이가 긴 수보다 작다면, 왼쪽에서부터 공백을 삽입해 길이를 맞춘다.
입력
첫째 줄에 네 정수 $r_1, c_1, r_2, c_2$가 주어진다.
출력
$r_2 - r_1 + 1$개의 줄에 소용돌이를 예쁘게 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
- $-5000 \leq r_1, c_1, r_2, c_2 \leq 5000$
- $0 \leq r_2 - r_1 \leq 49$
- $0 \leq c_2 - c_1 \leq 4$
풀이
문제 설명만 보면 매우 간단하다. 소용돌이 만드는 예제는 대학교 1학년 때 만들어 본 경험이 있어서, 소용돌이를 만들어 저장해두고 범위에 맞춰 출력하면 될 것처럼 보인다.
그런데, 만들어야하는 소용돌이의 크기가 문제다. 입력으로 주어진 소용돌이의 크기는 최대 $10001 \times 10001$이다. 소용돌이 중 최댓값이 약 1억이기 때문에, 이것을 모두 저장할 배열은 메모리상 만들 수 없다.
다행히도, 문제에서 원하는 소용돌이 크기는 $50 \times 5$ 크기이다. 소용돌이를 만들면서 범위에 들어가는 수들만 따로 저장해두고 출력하는 방식을 사용하자. 모든 칸을 채웠다고 굳이 전체 소용돌이를 완성하지 않아도 된다. 다만 알고리즘은 모든 소용돌이를 만드는 것을 전제로 해야한다.
그냥 소용돌이를 만드는 과정에서, 이 문제를 해결하기 위해 추가로 고려해야할 사항은 아래와 같다.
- 현재 채우고 있는 칸이 문제에서 출력을 원하는 칸인지 확인한다.
- 만약 원하는 칸이라면 따로 저장해둔다.
- 모든 칸을 채웠다면 소용돌이 만드는 것을 중단하고, 정답을 출력한다.
- 이 때, 자릿수를 맞추어 소용돌이를 예쁘게 출력해야한다.
정리해놓고 보면 생각보다 어렵지 않다. 사실 소용돌이를 만드는 것 자체가 가장 어려운 일일 것이다. 소용돌이를 만드는 과정은 시작점이 어디인지, 회전 규칙이 어떻게 되는지 그리고 현재 방향으로 몇 번 진행하는지의 규칙을 찾고 구현하면 된다. 이 부분의 설명은 따로 적지 않을 것이다.
- 참고 알고리즘 :
코드
사용 언어 : C
최종 수정일 : 2023 / 1 / 11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <stdio.h>
typedef struct Node {
int x, y;
} ND;
ND dir[4] = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} };
int digit[11] = {1, 10, 100, 1000, 10000, 100000, (int)(1e6), (int)(1e7), (int)(1e8), (int)(1e9)};
int currentDigit = 0;
int grid[50][5];
int r1, c1, r2, c2;
void fill_table() {
ND cur = (ND){-1, 0};
int currentDirection = 3, curLen = 1;
int fillCount = (r2 - r1 + 1) * (c2 - c1 + 1);
int x = 0;
while (fillCount > 0) {
for (int i = 0; i < curLen; ++i) {
cur.x += dir[currentDirection].x, cur.y += dir[currentDirection].y;
++x;
if (r1 <= cur.x && cur.x <= r2 && c1 <= cur.y && cur.y <= c2) {
grid[cur.x - r1][cur.y - c1] = x;
--fillCount;
}
if (digit[currentDigit] == x) {
++currentDigit;
}
if (fillCount == 0) {
return;
}
}
switch (currentDirection) {
case 0: {
currentDirection = 1;
break;
}
case 1: {
currentDirection = 2;
++curLen;
break;
}
case 2: {
currentDirection = 3;
break;
}
case 3: {
currentDirection = 0;
if (x > 1) {
++curLen;
}
break;
}
}
}
return;
}
void print_table() {
for (int i = 0; i <= r2 - r1; ++i) {
for (int j = 0; j <= c2 - c1; ++j) {
switch (currentDigit) {
case 1: {
printf("%1d ", grid[i][j]);
break;
}
case 2: {
printf("%2d ", grid[i][j]);
break;
}
case 3: {
printf("%3d ", grid[i][j]);
break;
}
case 4: {
printf("%4d ", grid[i][j]);
break;
}
case 5: {
printf("%5d ", grid[i][j]);
break;
}
case 6: {
printf("%6d ", grid[i][j]);
break;
}
case 7: {
printf("%7d ", grid[i][j]);
break;
}
case 8: {
printf("%8d ", grid[i][j]);
break;
}
case 9: {
printf("%9d ", grid[i][j]);
break;
}
case 10: {
printf("%10d ", grid[i][j]);
break;
}
}
}
printf("\n");
}
return;
}
int main() {
scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
fill_table();
print_table();
return 0;
}
dir[]: 동서남북 4가지 방향을 기록digit[]: 자릿수를 확인하기 위한 배열currentDigit: 현재까지 채운 소용돌이 수가 몇자리 수인지 기록
grid[][]: 문제에서 원하는, 소용돌이의 일부분을 저장할 배열fill_table(): 소용돌이를 채워가는 함수print_table(): 만들어진 소용돌이를 자릿수에 맞춰 출력하는 함수