2. 문제 요약: N, r, c가 주어진다. Z자 모양으로 재귀적으로 정의된 형태에 따라 2^N 크기의 2차원 정사각형 격자에 방문할 때, (r, c)는 몇 번째로 방문하는가?
3. 문제 접근 방법
첫 번째 문제 접근 방법
(r ,c)에 몇 번째로 방문하는지는, 격자를 나타내는 2차원 배열에서 [r][c] 인덱스의 값과 같다.
따라서, 문제에 주어진 대로 격자를 그려 넣은 뒤 (r, c)를 넣는다.
처음에는 Swift로 짰으나, 배열을 가리키는 배열 슬라이스에 할당이 가능하지 않아 C로 바꾸었다.
우선, 만일 2x2 격자인 경우 4번 카운트를 더해서 값을 넣는다. 2x2 격자가 아닌 경우, 격자를 4개로 쪼개서 4개를 Z자 순서에 맞게 다시 같은 함수에 넣는다.
격자를 잘 쪼개기 위해서, 격자 한 변의 길이와, 왼쪽 위의 x, y 좌표값을 함께 넘겨준다.
이렇게 풀면 입력 예제에 맞게 정답이 잘 나온다.
하지만, 실제로 제출하면 메모리 초과가 뜬다.
두 번째 문제 접근 방법
메모리 초과를 보고 충격에 빠져서 게임을 하다 보니, 한 번에 함수를 4번씩 호출할 필요가 없다는 것을 깨달았다. 문제에서 요구하는 것은 (r, c)에 대한 정보이므로, (r, c)와 완전히 관련이 없는 경우 작업을 수행하지 않아도 된다.
대신, 수행하지 않은 작업을 고려하여 카운트를 늘려 주어야 한다. 이때는 격자의 한 변의 크기를 이용한다.
이렇게 풀면 훨씬 빨리 답이잘 나온다.
그리고 제출하면 또 메모리 초과가 뜬다.
세 번째 문제 접근 방법
백준 서버가 터져서 다시 게임을 하다가, 반드시 2차원 배열을 할당하여 직접 그려 보지 않아도 된다는 것을 깨달았다. 두 번째 문제 접근 방법에서도 일부만 그렸듯이, 실제론 그리지 않고 '그렸다고 치고' 카운트 값을 세면 된다.
배열을 동적 할당할 때, O(2^N)이므로 이것이 사라지게 된다.
이렇게 풀면 맞았습니다!!가 뜬다.
4. C 코드
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
|
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int cnt;
int N, r, c;
int size;
void dot(int x, int y, int leng)
{
if(leng == 2)
{
if (x == (r+1) && y == (c+1)) {
cnt += 0;
}
else if(x == (r+1) && y < (c+1)) {
cnt += 1;
}
else if(x < (r+1) && y == (c+1)){
cnt += 2;
}
else if(x < (r+1) && y < (c+1)) {
cnt += 3;
}
}
else
{
const int target_x = r + 1;
const int target_y = c + 1;
if(target_x < x + leng / 2)
{
if(target_y < y + leng / 2)
{
dot(x, y, leng / 2); //왼쪽 위
}
else
{
cnt += leng * leng / 4;
dot(x, y + leng / 2, leng / 2); // 오른쪽 위
}
}
else
{
cnt += leng * leng / 2;
if(target_y < y + leng / 2)
{
dot(x + leng / 2, y, leng / 2); // 왼쪽 아래
}
else
{
cnt += leng * leng / 4;
dot(x + leng / 2, y + leng / 2, leng / 2); // 오른쪽 아래
}
}
}
}
int main(void)
{
scanf("%d %d %d", &N, &r, &c);
size = pow(2, N);
// int **arr = (int**)malloc(sizeof(int*) * (size + 1));
// for(int i = 0; i <= size; i++)
// arr[i] = (int*)malloc(sizeof(int) * (size + 1));
dot(1, 1, size);
printf("%d\n", cnt);
}
| cs |
댓글 없음:
댓글 쓰기