[백준문제풀이] 1074 Z

 

풀이일시 : 2020-09-24

​

 

문제 :

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

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

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

 

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

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

​

 

입력 :

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

ex)

2 3 1

​

 

출력 :

r행 c열을 몇 번째로 방문했는지 출력한다.

ex)

11

​

 

제한 :

1 <= N <= 15

0 <= r,c <2^N

​

 

풀이 :

분할정복 문제이다.

2차원 배열을 Z모양으로 탐색한다. 2^N 형태가 되었을 때는 배열을 등분하여 Z모양으로 탐색할 것이다.

분할을 통해 최소단위인 2*2 크기까지 나누고 시작한다.

 

dbstndi6316.tistory.com/65

[기본문제풀이] 분할정복

#include <iostream>
#include <math.h>
using namespace std;

int N, R, C;
int ans = 0;

void solve(int n, int r, int c) { //2^N, 0, 0으로 처음 들어온다.
	//네개로 분할하다가 마지막 2*2가 됐을때 탐색
	if (n == 2)
	{
		if (r == R && c == C) { //그 점을 탐색
			cout << ans;
			return;
		}

		ans++; //아니니깐 ++

		if (r == R && c + 1 == C) { //열+1 점을 탐색
			cout << ans;
			return;
		}

		ans++; //아니니깐 ++

		if (r + 1 == R && c == C) { //행+1 점을 탐색
			cout << ans;
			return;
		}

		ans++; //아니니깐 ++

		if (r + 1 == R && c + 1 == C) { //행+1 열+1 점을 탐색
			cout << ans;
			return;
		}

		ans++; //아니니깐 ++
		return; //이번 Z는 틀렸어 -> ans++ 네번 해줌의 성과
	}
	//네개로 계속하여 분할하는 코드
	solve(n / 2, r, c); //행,열로 봤을때 왼쪽 위 사각형
	solve(n / 2, r, c + n / 2); //오른쪽 위 사각형
	solve(n / 2, r + n / 2, c); //왼쪽 아래 사각형
	solve(n / 2, r + n / 2, c + n / 2); //왼쪽 위 사각형
}

int main() {
	scanf_s("%d %d %d", &N, &R, &C);
	solve(pow(2,N),0,0);
	return 0;
}

 

추가자료 : 수식함수들

dbstndi6316.tistory.com/32

[개념정리] C++ 수식함수들