BOJ 1074 - Z

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

재귀로 완전탐색하는 기본문제를 찾다가 접한 문제다.

 

주어진 입력을 4분할해서 좌상단 우상단 좌하단 우하단 순으로 방문하고 기저를 잘 처리해주면 되겠다 해서 처음으로 짠 코드. cnt[][] 2차원 배열로 방문 순서를 저장할까 했지만, 그냥 cnt=0부터 한개씩 올려주면서 처리하는 것으로 했다.

#include <cstdio>

int n, r, c;
int cnt, rst;
void go(int cy, int cx, int n) {
	if (n == 0) {
		if (cy == r && cx == c) rst = cnt;
		cnt++;
		return;
	}
	go(cy, cx, n - 1);
	go(cy, cx + (1 << (n - 1)), n - 1);
	go(cy + (1 << (n - 1)), cx, n - 1);
	go(cy + (1 << (n - 1)), cx + (1 << (n - 1)), n - 1);
}

int main() {
	scanf("%d %d %d", &n, &r, &c);
	go(0, 0, n);
	printf("%d\n", rst);
}

결과는 시간초과. 한 변의 최대 길이는 2^15이이므로 방문하는 칸이 2^30이 돼서 시간초과가 난 것 같다.

 

문제 풀 때 시간복잡도를 완전 잘못 생각해서 기저에서 4번의 비교를 하므로 의미는 없지만 재귀의 깊이를 한 칸 줄여봤는데 정답이 떳다. ???아직도 이게 정답인 이유를 모르겠다. 

#include <cstdio>

int n, r, c;
unsigned long long cnt, rst;
void go(int cy, int cx, int n) {
	if (n == 1) {
		
		if (cy == r && cx == c) {
			rst = cnt;
		}
		cnt++;
		if (cy == r && cx+1 == c) {
			rst = cnt;
		}
		cnt++;
		if (cy+1 == r && cx == c) {
			rst = cnt;
		}
		cnt++;
		if (cy+1 == r && cx+1 == c) {
			rst = cnt;
		}
		cnt++;
		return;
	}
	go(cy, cx, n - 1);
	go(cy, cx + (1 << (n - 1)), n - 1);
	go(cy + (1 << (n - 1)), cx, n - 1);
	go(cy + (1 << (n - 1)), cx + (1 << (n - 1)), n - 1);
}

int main() {
	scanf("%d %d %d", &n, &r, &c);
	go(0, 0, n);
	printf("%llu\n", rst);
}

 

 

좀 최적화를 할 수 있는 방법을 생각하다가, 어차피 cnt[][]배열을 채울 것이 아니라면 r,c가 포함되지 않은 블럭은 단순 연산으로 알아낼 수 있으므로 칸의 크기에 맞게 cnt를 조정해줬다.

#include <cstdio>
int n, r, c;
int cnt, rst;
void go(int cy, int cx, int n) {
	//{r,c}가 포함되지 않은 블럭이면 cnt조정후 return해버리기
	if ((r<cy || r>=cy+(1<<n)) || (c<cx || c>=cx+(1<<n))) {
		cnt += (1<<n*2);
		return;
	}
	if (cy == r && cx == c) {
    	rst = cnt;
		return;
	}
	
	go(cy, cx, n - 1);
	go(cy, cx + (1<<n-1), n - 1);
	go(cy + (1 << n - 1), cx, n - 1);
	go(cy + (1 << n - 1), cx + (1 << n - 1), n - 1);
}

int main() {
	scanf("%d %d %d", &n, &r, &c);
	go(0, 0, n);
	printf("%d\n", rst);
}

재귀가 들어가는 부분을 1/4로 단축했으니까 최악의 경우 O(loglong(2^30))쯤 될 것 같다.

 

.후기

딱 이정도 난이도가 내게 적당한 것 같다