c언어 1074번 Z (백준)

#include <stdio.h>
#include <stdlib.h> //강제종료를 위한 exit() 사용

long long int ans = 0; //몇번째 인지를 나타내는 변수
int n, r, c; //입력 받을 변수

void loop(int x, int y, long long int k, long long int size) //분할 정복
{
	if(k > 1) { //4등분으로 계속 계속 쪼갠다.
		long long int tmp = k/2;
		long long int tmp2 = size/4;
		if(c < x + tmp) { //제1, 3사분면
			if(r < y+tmp) loop(x, y, tmp, tmp2); //제1사분면
			else { //제3사분면
				ans += 2*tmp2;
				loop(x, y+tmp, tmp, tmp2);
			}
		} else { //제2, 4사분면
			if(r < y+tmp) {//제2사분면
				ans += tmp2;
				loop(x+tmp, y, tmp, tmp2);
			} else {//제4사분면
				ans += 3*tmp2;
				loop(x+tmp, y+tmp, tmp, tmp2);
			}
		} //k==1 즉 더 이상 쪼갤 수 없을 때가 r행 c열에 도달함을 의미한다.
	} else printf("%lld", ans);
}

int main(void)
{
	scanf("%d %d %d", &n, &r, &c);
	
	int i = 0;
	long long int sum = 1; //사각형을 4등분 하기 위한 변수
	long long int size = 1; //전체 사각형의 크기
	while(i++ < n) { //제곱
		sum *= 2;
		size *= 4;
	}
	loop(0, 0, sum, size); //분할 정복
}

 

 

풀이

1. r행, c열에 도달할 때까지 정확히 4등분을 한다.

2. 제1, 2, 3, 4사분면에 갈 때마다 각각 (현재 사각형의 크기/4)을 *0, *1, *2, *3 씩 하여 ans에 더해준다. 

ex) 사각형의 크기는 16이며, 찾고자 하는 것이 제4사분면에 있으면, 나머지 제1, 2, 3 사분면의 크기를 ans에 더해준다.

ans += (size/4) * 3;

3. 더이상 나눌 수 없을 때가 r행, c열에 도달했다는 의미이며, 그때의 ans 즉 번호를 출력한다.

4. 거기서 바로 종료하기 위해 exit(0)을 이용한다. 

 

1074번: Z (acmicpc.net)

1074번: Z