[백준 BOJ 1074 silver1 - Z] 분할정복 C++

백준 Z https://www.acmicpc.net/problem/1074

1074번: Z

 

[시간 초과 코드]

int N, r, c;
int cnt;

void count(int sx, int sy, int ex, int ey) {
	//cout << sx << sy << ex << ey;
	if (sx == ex && sy == ey) {
		cnt++;
		if (sx == r && sy == c) cout << cnt-1;
		return;
	}
	int cmid = (sy + ey) / 2;
	int rmid = (sx + ex) / 2;
	count(sx, sy, rmid, cmid);
	count(sx, cmid + 1, rmid, ey);
	count(rmid + 1, sy, ex, cmid);
	count(rmid + 1, cmid + 1, ex, ey);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> r >> c;
	int len = 1;
	for (int i = 0; i < N; i++) {
		len *= 2;
	}
	count(0, 0, len - 1, len - 1);
}

처음에는 단순히 재귀를 돌며 0부터 구하려는 위치까지 숫자를 다 세는 코드로 작성했다. 

그런데 시간초과가 났다. 이문제 조건이 0.5초이다. 

N의 최대는 15이고, 그러면 한 변 최대 길이는 약 33000 정도이다. 33000*33000 은 약 10억이므로 시간초과가 날 수 밖에 없었다. 

 

현재 배열에서 4개로 나누고 재귀로 모두 호출할 필요 없이 구하려는 위치가 속한 부분만 재귀호출 해주도록 수정하였다. 이때 주의할 점은 포함된 부분만 호출하면서 탐색 순서를 수정해주는 것이다. 

 

 

---

 

계속 4개씩 나누면서, 구하려는 위치(r,c)가 포함된 곳만 재귀호출을 하는 코드로 수정했다.

이때 방문하는 순서는 나눌 때 (전체칸수/4) 를 첫번째 칸 순서에서 알맞게 더해주면 된다.

 

using namespace std;

int N, r, c;
int cnt;
int len = 1;

void count(int sx, int sy, int ex, int ey) {
	if (sx == ex && sy == ey) { //1칸짜리
		cnt++;
		if (sx == r && sy == c) cout << cnt - 1 << "\n"; //r행 c열
		return;
	}
	int cmid = (sy + ey) / 2;
	int rmid = (sx + ex) / 2;
	int total = (ey - sy + 1) * (ex - sx + 1) / 4;

	if (r >= sx && r <= rmid && c >= sy && c <= cmid) {
		count(sx, sy, rmid, cmid);
	}
	else if (r >= sx && r <= rmid && c > cmid && c <= ey) {
		cnt += total;
		count(sx, cmid + 1, rmid, ey);
	}
	else if (r > rmid && r <= ex && c >= sy && c <= cmid) {
		cnt += total * 2;
		count(rmid + 1, sy, ex, cmid);
	}
	else if (r > rmid && r <= ex && c > cmid && c <= ey) {
		cnt += total * 3;
		count(rmid + 1, cmid + 1, ex, ey);
	}
	return;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> r >> c;
	len = 1;
	for (int i = 0; i < N; i++) {
		len *= 2;
	}
	int big = len * len;

	count(0, 0, len - 1, len - 1);
}