[C/C++] 백준 1074번 - Z (분할정복)

 

문제

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

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

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

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

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

입력

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

출력

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

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2^N

 

 

<코드>

#include<iostream>
#include<algorithm>
using namespace std;

int N, C, R;
long long ans;
void solve(int n, int c, int r)
{
	if (n == 0) return;

	int size = 1 << n;
	long long half = size / 2;

	if (c / half == 0 && r / half == 0)
	{
		ans += half * half * 0;
		solve(n - 1, c % half, r % half);
	}
	else if (c / half == 0 && r / half == 1)
	{
		ans += half * half * 1;
		solve(n - 1, c % half, r % half);
	}
	else if (c / half == 1 && r / half == 0)
	{
		ans += half * half * 2;
		solve(n - 1, c % half, r % half);
	}
	else // (c / size == 1 && r / size == 1)
	{
		ans += half * half * 3;
		solve(n - 1, c % half, r % half);
	}
}

int main()
{
	cin >> N >> C >> R;
	solve(N, C, R);
	cout << ans << '\n';
}

 

풀이 방법

분할 정복으로 해결하였는데, 먼저 전체를 4등분 한 뒤 c와 r을 통해서 해당하는 행과 열이 몇 번 그룹에 속하는지 판단합니다.

예제 입력 2와 같이 N, c, r이 3,7,7이 주어졌을 때 배열의 사이즈는 2의 3승인 8이고 half라는 변수를 size의 절반으로 정의할 때 c/half, r/half를 통해서 몇 번 그룹인지 알 수 있게 됩니다.

• (c / half, r / half) == (0, 0)이라면 1번 그룹
• (c / half, r / half) == (0, 1)이라면 2번 그룹
• (c / half, r / half) == (1, 0)이라면 3번 그룹
• (c / half, r / half) == (1, 1)이라면 4번 그룹

c와 r은 7, 7이므로 

c == 7 / 4 == 1

r == 7 / 4 == 1

 

으로 4번 그룹에 속하게 되고 재귀로 solve(n - 1, c % half, r % half)를 호출하게 됩니다.

그리고 호출하기 전에 ans값에는 half*half*3 = 4*4*3 = 48 만큼을 더해줍니다. 

(만약 1번 그룹이었다면 0을, 2번 그룹이었다면 16을, 3번 그룹이였다면 32를 더해줬을 겁니다.)

이제 n = 2, c = 3, r = 3이므로 다시 계산해보면 (c / half, r / half)는 (1, 1)로 4번 그룹인 것을 알 수 있고
재귀로 solve(n - 1, c % half, r % half)를 호출하게 됩니다.
그리고 호출하기 전에는 ans값에 half*half*3 = 2*2*3 = 12를 더해줍니다.

 

이제 n = 1, c = 1, r = 1이므로 (c / half, r / half)는 (1, 1)로 4번 그룹이며 ans값에 half*half*3 = 1*1*3 = 3을 더해줍니다. 그리고 재귀로 n = 0이 파라미터로 전달되므로 함수는 종료되고

최종으로 ans = 48 + 12 + 3 = 63이 정답이 됩니다.

 

 

 

 

www.acmicpc.net/problem/1074

1074번: Z