🎲문제

---

주소:백준 1074

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

https://upload.acmicpc.net/21c73b56-5a91-43aa-b71f-9b74925c0adc/-/preview/

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

https://upload.acmicpc.net/adc7cfae-e84d-4d5c-af8e-ee011f8fff8f/-/preview/

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

https://upload.acmicpc.net/d3e84bb7-9424-4764-ad3a-811e7fcbd53f/-/preview/

⌨ 입력

---

첫째 줄에 정수 N, r, c가 주어진다.

✅ 풀이

---

풀이방법

N을 4의 N 제곱으로 생각하면 전체 테이블의 크기로 생각할 수 있으므로 N을 하나씩 감소시키면서 재귀적으로 Z모양으로 순서를 정해준다. N이 0일때 0을 반환하고, 1일때는 0,1,2,3중 하나 2일때는0,4,8,12와 같은 숫자를 N-1의 값과 더해주는 방식으로 동작한다.

1. N,r,c를 입력받는다.

void init() {
	cin >> N >> r >> c;
}

1. N = 0일 때 0을 리턴하도록 만든다.
2. 4^N 을 전체크기, 전체크기의 제곱근을 한변의 길이로 놓는다.
3. 전체 넓이의 테이블을 4부분으로 나눈다.
4. r과 c를 조사해서 4부분 중 한 부분에 해당한다면 해당 부분의 첫 번째 칸을 더한 값 + (해당부분테이블 + N-1)을 인자로한 재귀함수를 반환한다.

int recursion(int rr, int cc) {

	if (N == 0)
		return 0;
	
	int asize = pow(4, N);
	N--;

	int row_size = sqrt(asize);

	if (0 <= rr && rr < row_size / 2 && 0 <= cc && cc < row_size / 2) {
		return recursion(rr,cc);
	}
	else if (row_size / 2 <= rr && rr < row_size && 0 <= cc && cc < row_size / 2) {
		return ((asize / 4) * 2 )  + recursion(rr - (row_size/2), cc);
	}
	else if (row_size / 2 <= rr && rr < row_size && row_size / 2 <= cc && cc < row_size) {
		return ((asize / 4)*3) + recursion(rr - (row_size/2), cc - (row_size / 2));
	}
	else if (0 <= rr && rr < row_size/2 && row_size / 2 <= cc && cc < row_size) {
		return (asize / 4) + recursion(rr, cc - (row_size / 2));
	}
}

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include<cmath>
#include<cstring>

using namespace std;

void init();
void solve();
int recursion(int,int);

int N, r, c;

void init() {
	cin >> N >> r >> c;
}

void solve() {

	cout << recursion(r,c);
}

int recursion(int rr, int cc) {

	if (N == 0)
		return 0;
	
	int asize = pow(4, N);
	N--;

	int row_size = sqrt(asize);

	if (0 <= rr && rr < row_size / 2 && 0 <= cc && cc < row_size / 2) {
		return recursion(rr,cc);
	}
	else if (row_size / 2 <= rr && rr < row_size && 0 <= cc && cc < row_size / 2) {
		return ((asize / 4) * 2 )  + recursion(rr - (row_size/2), cc);
	}
	else if (row_size / 2 <= rr && rr < row_size && row_size / 2 <= cc && cc < row_size) {
		return ((asize / 4)*3) + recursion(rr - (row_size/2), cc - (row_size / 2));
	}
	else if (0 <= rr && rr < row_size/2 && row_size / 2 <= cc && cc < row_size) {
		return (asize / 4) + recursion(rr, cc - (row_size / 2));
	}
}

int main() {
	init();
	solve();
}