[BOJ] 백준 1074번 Z

링크

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

문제

입력

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

출력

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

풀이

 #include <iostream>

using namespace std;
int n, r, c;

int func(int n, int r, int c) {
	if (n == 0) 
		return 0;//base condition
	int half = 1 << (n - 1); //비트연산자 2^(n-1) -> 한 변의 절반
	if (r < half && c < half) 
		return func(n - 1, r, c);//첫번째 칸일때
	if (r < half && c >= half) 
		return half * half + func(n - 1, r, c - half);//두번째 칸일때
	if (r >= half && c < half) 
		return half * half * 2 + func(n - 1, r - half, c); //세번째 칸일때
	return half * half * 3 + func(n - 1, r - half, c - half);//네번째 칸일때
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> r >> c;
	cout << func(n, r, c);
}

설명

전체 배열을 4등분을 한다.
n=k일때 결과를 가지고 n=k+1일때 써먹을 수 있다. 즉 재귀적인 형태다.

half는 한변의 절반 : 2^(n-1)

source 바킹독 0x0B