[백준 / C언어] 1074번: Z

https://www.acmicpc.net/problem/1074

1074번: Z

 

난이도: solved.ac 실버 1

 

알고리즘 분류

---

재귀, 분할 정복

 

접근 방법 및 구현

---

찾아야 할 r행 c열의 숫자가 4등분 한 사각형 중 어느 부분에 있는지에 집중했다.

그리고 찾아야 할 좌표를 목표로 N = 0의 크기 즉, 한 칸짜리의 사각형이 될 때까지 4등분 해주었다.

 

N = 3일 때 2행 5열의 숫자를 찾아야 한다고 해보자.

N = 3일 때는 아래의 그림처럼 0~7행, 0~7열을 가진 배열이 그려진다. 참고로 배열은 2^N * 2^N의 크기를 가진다.

 

큰 사각형을 4등분해서 생기는 4개의 사각형에서 왼쪽 위 사각형을 0번, 오른쪽 위 사각형을 1번, 왼쪽 아래 사각형을 2번, 오른쪽 아래 사각형을 3번 사각형이라고 부르자.

2행 5열은 1번 사각형에 속한다.

 

1번 사각형의 사이즈는 N = 2일 때 생기는 사각형과 같아진다. (4 * 4 크기)

아래의 그림처럼 우리가 찾아야 할 2행 5열의 위치는, 줄어든 크기의 사각형에서 2행 1열의 위치가 된다.

이는 현재 사각형의 범위를 초과하는 5(열)에서 이전의 큰 사각형 한 변의 길이의 절반을 뺀 것이다.

 

5열 - (8/2) = 1열

→ 2행 1열

 

이제 N = 2 사이즈에서는 2행 1열의 번호를 찾아야 한다. 이 사각형을 4등분 하고 나서 2행 1열은 2번 사각형에 들어가게 된다.

위와 똑같이 N = 1로 줄어들고 나서는 2행 1열을 0행 1열로 바꿔준다.

 

N = 2에서 사각형의 한 변의 길이: 4

2행 - (4/2) = 0행

→ 0행 1열

 

N = 1에서도 마찬가지로 N = 0의 크기를 가지도록 4등분 해주었는데, 그 후의 0행 1열은 0행 0열이 된다.

이제 N = 0이 되었으므로 재귀 호출을 멈춘다.

 

 

그리고 큰 사각형을 4등분을 하고난 뒤의 각 첫자리의 숫자가 무엇인지에도 집중을 했다.

4등분을 하고난 뒤 각 첫자리의 숫자는 아래와 같은 규칙을 가졌다.

 

2행 5열의 숫자를 찾기 위해 계속 4등분을 할 때 동시에 위처럼 n * 4^(N-1) (n번 사각형: 0, 1, 2, 3)의 값을 더해주었다.

 

N = 3 (2행 5열)

order = 16

 

N = 2 (2행 1열)

order = 16 + 2*4 = 24

 

N = 1 (0행 1열)

order = 24 + 1*1 = 25

 

N = 0 (0행 0열)

order = 25

 

∴ 2행 5열의 order = 25

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

void find(int N, int r, int c);
int order = 0;

int main() {
	int N, r, c;
	scanf("%d %d %d", &N, &r, &c);
	find(N, r, c);
	printf("%d", order);
	return 0;
}

void find(int N, int r, int c) {
	if (N != 0) {
		int width = 1, size = 1;
		for (int i = 1; i < N; i++) {
			width *= 2;
			size *= 4;
		}
		if (r < width) {
			if (c < width) {
				find(N - 1, r, c);
			}
			else {
				order += size;
				find(N - 1, r, c - width);
			}
		}
		else {
			if (c < width) {
				order += 2 * size;
				find(N - 1, r - width, c);
			}
			else {
				order += 3 * size;
				find(N - 1, r - width, c - width);
			}
		}
	}
}