[백준 BOJ] 1074 Z

링크

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

 

풀이

Z가 많이 그려져 있습니다.

 

이렇게 $2^{n}$를 기준으로 4등분 해서 (r,c)가 어디 있는지 알아냅니다.

분할 정복 알고리즘으로 크게 4등분으로 쪼개고 더 잘게 잘게 쪼개가면서 답을 찾는 알고리즘입니다.

 

 

2 3 1이라는 입력 예제로 테스트 해보겠습니다.

 

n이 2일 때, $2^{n}$는 2가 됩니다.

r은 3이고 c는 1이기 때문에 r은 2보다 크거나 같고 c는 2보다 작은 3사분면이 해당됩니다.

ans에는 $2\times 2^{n}$을 더하고, r과 c에는 $2^{n}$인 2로 나눈 나머지를 대입합니다.

 

 

n이 1일 때, $2^{n}$는 1이 됩니다.

r은 1이고 c는 1이기 때문에 r은 1보다 크거나 같고 c는 1보다 크거나 같은 4사분면이 해당됩니다.

ans에는 $3\times 2^{n}$을 더하고, n이 1이니 종료합니다.

 

이렇게 ans는 8+3이 되어 11이라는 답을 찾을 수 있습니다.

 

 

코드

//1074_Z
#include <cstdio>
#include <math.h>
using namespace std;

int n, r, c, ans, s;

int main() {
	scanf("%d %d %d", &n, &r, &c);

	while (n) {
		int idx;
		s= pow(2, n)/2;
		if (c < s && r < s) idx = 0;		//2사분면
		else if (c >= s && r < s) idx = 1;	//1사분면
		else if (c < s&&r >= s)idx = 2;		//3사분면
		else if (c >= s && r >= s)idx = 3;	//4사분면

		c %= s;		
		r %= s;		//c와 r을 다음 사각형으로 세팅

		ans += pow(s,2) * idx;		// ans에 s^2 * idx 더해줌
		n--;
	}

	printf("%d\n", ans);

	return 0;
}