1074번 : Z

처음엔 재귀함수로 짜다가 시간초과가 나서 수학적으로 접근해 보았습니다.

쪼개는 방법은 단순합니다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 쪼개죠.

쪼개는 기준도 단순합니다. 처음 시작할 때 2^(N-1)의 길이로 자르고 자르는 것을 반복할 때마다 1/2씩 줄어듭니다.

 

N=2일 때, (3, 1) 자리 숫자를 알고 싶다면

1) 범위(쪼개는 길이)가 2일 때 : x=3/2=1, y=1/2=0 이므로 왼쪽 아래자리, x와 y에 각각 2로 나눈 나머지를 저장하고 범위를 2로 나눕니다.

2) 범위가 1일 때 : x=1/1=1, y=1/1=1 이므로 오른쪽 아래자리.

 

이때

1)에선 범위의 제곱 * 2만큼 res에 더해줍니다.(0 + 2^2 * 2 = 8)

2)에선 범위의 제곱 * 3만큼 res에 더해줍니다.(8 + 1^2 * 3 = 11)

 

자세한 내용은 코드에..

#include <stdio.h>
#include <math.h>
int N, r, c;

int main() {
	scanf("%d %d %d", &N, &r, &c);
	int range = (int)pow(2, N);
	range /= 2;
	int a = r, b = c;
	int res = 0;
	for (int i = N; i > 0; --i) {
		int x, y;
		x = a / range;
		y = b / range;
		//printf("x : %d, y : %d\n", x, y);
		if (x == 0 && y == 0) {
			res += 0;
		}
		else if (x == 0 && y == 1) {
			res += (range*range) * 1;
		}
		else if (x == 1 && y == 0) {
			res += (range*range) * 2;
		}
		else if (x == 1 && y == 1) {
			res += (range*range) * 3;
		}
		a %= range;
		b %= range;
		range /= 2;
	}
	printf("%d", res);
}