BaekJoon 1074 Z

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

소스결과 2172 KB / 0 ms

출처 Baekjoon

언어 C++ 17

분류 수학, 분할 정복, 재귀 호출

 

설명

그림과 같이 2^N by 2^N 배열을 Z 모양으로 순차적으로 방문한다고 할 때 r, c 좌표의 값이 몇 번째로 방문이 되는지를 알아내는 문제

 

수학 탭에서 문제를 발견해 들어왔다. 기존 문제들이 r, c가 주어진다면 특정 공식에 의해 값이 추출 되는 방식이어서 여러 값을 넣어 보면서 공식을 유도 하려 했으나... 대각선을 기준으로 값이 0번 행의 값이 0번 열의 값의 절반이라는 사실밖에 못찾았다. 아무 의미 없는 공식이다.

문제 자체에서 Z 배치가 재귀 호출로 만들어지기에 분류에 재귀 호출이 있는 거라고 생각해 문제 해결에 더 오래 걸린 것 같다.

 

정답은 r, c 가 몇 번째 N에 있는 지를 기준으로 좌상, 우상, 좌하, 우하단에 있는지를 판별하고 범위를 좁혀 가면서 r, c 에 도착했을때 값을 출력하면 되는 문제였다.

정답 자체를 구하는 과정에서 재귀 호출을 사용했기에 분류에 포함이 되었다 싶다.

 

괜히 어렵게 생각했다...

 

알고리즘

1. r, c를 통해 구하려는 좌표가 몇 번째 N에 속하는 지 확인한다. ( 연산 횟수를 조금 줄이기 위한 부분 )

2. 구하려는 좌표의 범위를 초기화 한 후, 1에서 구해는 N을 가지고 값의 최대 범위를 지정해준다.

3. 시작 좌표와 끝나는 좌표를 기준으로 4등분 한뒤 좌상, 우상, 좌하, 우하단에 있는 지 판단해서 함수를 재귀 호출한다.

4. 시작 좌표가 r, c 위치에 도달하면 재귀함수 호출을 종료후 값을 반환한다.

 

소스코드

#include <iostream>
#include <cmath>

using namespace std;

int n, r, c;

int solve(int sX, int eX, int sY, int eY, int startV, int endV)
{
	if (sX == c && sY == r)
		return startV;

	int halfX = (sX + eX) / 2;
	int halfY = (sY + eY) / 2;
	int quarter = (endV - startV) / 4;
	if (sX <= c && c < halfX && sY <= r && r < halfY) // left top
		return solve(sX, halfX, sY, halfY, startV, startV + quarter);
	else if (halfX <= c && c < eX && sY <= r && r < halfY) // right bottom
		return solve(halfX, eX, sY, halfY, startV +quarter, startV + (quarter * 2));
	else if (sX <= c && c < halfX && halfY <= r && r < eY) // left bottom
		return solve(sX, halfX, halfY, eY, startV + (quarter * 2), startV + (quarter * 3));
	return solve(halfX, eX, halfY, eY, startV + (quarter * 3), endV); // right top
}

int main()
{
	int i;
	cin >> n >> r >> c;

	for (i = 1; !(r < pow(2, i) && c < pow(2, i)); i++); // get N

	cout << solve(0, pow(2, i), 0, pow(2, i), 0, pow(2, i) * pow(2, i));

	return 0;
}