[알고리즘] 백준 1074번: Z (C++), 단순한 재귀가 아닌 분할 정복

이번 문제도 분할 정복이다. 다만 이번 문제는 2차원 배열을 사용하지 못한다.

32769 x 32769 사이즈의 배열을 선언해야 했어서 이는 엄청 크기 때문에 선언하지 못한다.

그래서 배열 없이 접근했다.

'0행의 0열 0부터 시작' 같은 키워드는 이번 문제에서 유독 헷갈렸었기 때문에 행과 열은 1부터 시작하고 1부터 시작하게 하여 마지막 결과 값에 -1을 해주었다.

분할 정복 함수에서 각 사분면에 해당하는 조건들을 달고, 함수의 재귀를 거치면서 입력한 행렬과 함수의 도출 행렬이 같다면 함수를 종료하고, 해당하는 결과 값에 -1을 해준 뒤에 출력하고 함수를 종료시켰다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 배열 사이즈가 너무 커진다. >> 꼭 배열을 써야할까
//int map[32769][32769] = { 0, };

int N, r, c;

void DaQ(int Nr, int Nc, int idx) {
	if (r == Nr && c == Nc) {
		cout << idx - 1;
		return;
	}

	// 시간초과가 여기서 나는 걸까
	// 그렇다기엔 4가지 경우 모두 재귀를 하지는 않는데

	if (r <= Nr / 2 && c > Nc / 2) { // 1사분면
		idx /= 2;
		DaQ(Nr / 2, Nc, idx);
	}
	else if (r <= Nr / 2 && c <= Nc / 2) { // 2사분면
		idx /= 4;
		DaQ(Nr / 2, Nc / 2, idx);
	}
	else if (r > Nr / 2 && c <= Nc / 2) { // 3사분면
		idx = idx / 2 + idx / 4;
		DaQ(Nr, Nc / 2, idx);
	}
	else if (r > Nr / 2 && c > Nc / 2) { // 4사분면
		DaQ(Nr, Nc, idx);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> r >> c;
	// 0부터 시작하니 헷갈린다 += 1로 한다
	r += 1; c += 1;
	// first 행 혹은 열 길이, second 해당하는 위치의 값
	int first = pow(2, N);
	int second = pow(4, N);
	DaQ(first, first, second);
	return 0;
}

하지만, 이는 시간 초과를 발생시킨다. 왜 시간 초과를 발생시키는지 알 수 없었다. 최댓값을 넣어볼 생각은 할 수가 없었다. 왜냐하면 '문제에서 이러한 코드를 유도하고, 이게 확실하지 않은가?'라는 오만한 생각 때문이었다. 시간 초과를 발생시키는지 알 수 없었던 이유는 이 코드에서는 4가지 재귀 함수를 다발적으로 발생시키지 않고, 조건에 따라 하나씩 실행시키기 때문에 더욱 시간 초과가 함수에서 나는 것이 맞을까라는 의심이 들었다.

---

문제가 무엇이었을까

문제를 파악할 수가 없어서 다른 분들의 답을 참고했다. 이 과정에서 알 수 있었던 건 같은 분할 정복이지만 코드의 방향은 달랐다.

(+참고 https://cocoon1787.tistory.com/376)

참고한 내용에 따르면 '아 이래서 분할 정복이지, 이게 분할 정복이구나'라고 느낀 건 있지만 그렇다고 해서 내 코드가 왜 시간 초과를 유발할까?라는 물음에는 아직 답을 구하지 못했다. (포스팅 글 적으며 계속 찾는 중)

 

찾은 거 같다! 😮😮 조금 민망한 실수 같다..

반례는 다음과 같다.

1. 15 32766 32767
2. 2 2 2

4 사분면으로 가는 코드에서는 변경되는 것이 아무것도 없다. 즉, 내 논리는 틀렸다.

한 번 4 사분면으로 가기 시작하면 무한 루프를 발생시키는 걸 내 손으로 작성해놓고 '뭐가 문제지'를 2시간 동안 봤다.

구했던 반례도 최댓값이라도 넣어보자 하다가 잘 나오는 걸 확인하고는 '바로 옆의 값은 뭐가 나올까'를 하다가 예외 처리가 계속 나길래 '함수가 계속 무한으로 콜 되어서 그런 거였구나'라는 것을 알 수 있었다. 그래서 채점에서도 '틀렸습니다'가 아닌 시간 초과를 계속 내놓았던 것이다.

 

---

참고했던 코드

아까 위에서 참고했던 코드를 보고 '아 이래서 분할 정복이구나'를 깨달았다고 했다. 그 이유는 코드를 보면서 설명하겠다.

#include <iostream>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;

ll answer = 0;

void DaQ(int N, int r, int c) {
	if (N == 0) {
		return;
	}

	int size = 1 << N; // 비트 연산자 : x2의 역할을 함
	ll half = size / 2;

	if (r / half == 0 && c / half == 0) {
		// 1구역(2사분면) 안에 있으므로 무언가를 더해줄 필요가 없다.
		// 보기편하게끔 작성한 코드
		answer += (half * half) * 0;
		DaQ(N - 1, r % half, c % half);
	}
	else if (r / half == 0 && c / half == 1) {
		answer += (half * half) * 1;
		DaQ(N - 1, r % half, c % half);
	}
	else if (r / half == 1 && c / half == 0) {
		answer += (half * half) * 2;
		DaQ(N - 1, r % half, c % half);
	}
	else {
		answer += (half * half) * 3;
		DaQ(N - 1, r % half, c % half);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, r, c;
	cin >> N >> r >> c;
	DaQ(N, r, c);
	cout << answer;
	return 0;
}

이번 문제의 핵심은 그 구역에 속해있는 것이 아니라면 그리고 그 구역을 Z자로 보았을 때 지나친 구역이라면 그 구역만큼 더해가다가 재귀를 통해 구역의 범위를 줄이면서 0이 되면 종료를 시키면 된다. 그림으로 보자.

 

다음과 같은 값을 구한다. (2행 3열)

2와 3 둘 다 half로 나눈 몫이 1 이상이기 때문에 맨 마지막 조건을 지나친다. 즉, 구역 3개를 지나친다는 소리다.

지금 현재 값은 0~11, 현재 answer는 12다. 두 번째 재귀에서는 0행 1열을 구하는 것이 되어있다. 그림상으로도 맞다. 그리고, 이는 2번째 조건을 만족하여 answer에는 1이 더해지고 n은 0이 되어 함수가 종료된다.

첫 재귀에서 12, 다음 재귀에서 1, 결론적으로 (12 + 1) = 13 이 부분에서 '이래서 분할 정복이구나'를 느꼈다.

---

이제야 분할 정복에 대해 조금씩 감이 잡히는 거 같다. 이전 분할 정복 문제에서도 '한 번 함수가 콜이 될 때 나오는 값들을 더하게끔 유도하면 되겠다'를 인지하고 있었지만 직접 겪으니 점점 선명해지는 거 같다.