[C++] 백준 1074번: Z

마땅히 넣을 이미지를 못 찾아서 Blender에서 직접 제작하여 렌더링했다. Blender를 오랜만에 다뤘는데 굉장히 많이 달라졌다.

문제 바로가기

이 문제를 재귀함수를 통해 풀 수 있을 것이라 생각했다.

큰 영역에서 시작해서 한 변의 길이를 절반씩 줄여나가며 그 길이가 2가 됐을 때,

네 칸에 Z 순서로 방문하여 순서를 저장하는 방식으로 코드를 구현했다.

다음 코드가 이 방식을 나타낸 코드 전문이다.

#include <iostream>

using namespace std;

// pivot: [r, c], interval : [2^N, K]
void move(int* table, int* pivot, int* interval, int& order) {
	// Step 1. If interval is minimum, Mark.
	if (interval[1] == 2) {
		int delta[4][2] = { {0, 0}, {0, 1}, {1, 0}, {1, 1} };
		for (auto& d : delta) {
			int r = pivot[0] + d[0];
			int c = pivot[1] + d[1];
			table[r * interval[0] + c] = order;
			order++;
		}
		return;
	}

	// Step 2. Slice into four space.
	int newInterval[2] = { interval[0], interval[1] / 2 };
	int newPivots[4][2] = {	{pivot[0]				, pivot[1]				},
					{pivot[0]				, pivot[1] + newInterval[1]	},
					{pivot[0] + newInterval[1]	, pivot[1]				},
					{pivot[0] + newInterval[1]	, pivot[1] + newInterval[1]	} };
	for (auto& newPivot : newPivots)
		move(table, newPivot, newInterval, order);
}

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

	int N, r, c;
	cin >> N >> r >> c;

	int length = 1;
	for (int i = 0; i < N; i++)
		length *= 2;

	int* table = new int[length * length];
	int pivot[2] = { 0, 0 };
	int interval[2] = { length, length };
	int order = 0;

	move(table, pivot, interval, order);

	cout << table[r * length + c] << "\n";

	delete[] table;
	return 0;
}

ideone에서 15 32767 32767을 stdin으로 설정하고 돌렸을 때 약 5초가 소요됐다. 메모리 소요도 꽤 컸다.

심지어 백준에 제출했을 땐, 런타임 에러가 발생하는데 과도한 재귀호출로 인한 문제인 것으로 판단된다.

따라서 재귀호출을 최소화할 필요가 있다. 질문답변에서 찾아보니 (r, c)가 포함되지 않는 영역은 수만 세고 넘어가는 식으로 재귀호출을 줄일 수 있다고 한다.

이를 참고하여 이번 영역에  (r, c)가 포함되지 않으면 order에 영역의 넓이 만큼 더한 후 넘어가는 코드를 추가했다.

#include <iostream>

using namespace std;

int N, r, c;

// pivot: [r, c], interval : [2^N, K]
void move(int* table, int* pivot, int* interval, int& order) {

	// Step 0. If there is no (r, c) in this area, Stop to go on.
	if ((r < pivot[0] || r >= pivot[0] + interval[1]) && (c < pivot[1] || c >= pivot[1] + interval[1])) {
		order += interval[1] * interval[1];
		return;
	}

	// Step 1. If interval is minimum, Mark.
	if (interval[1] == 2) {
		int delta[4][2] = { {0, 0}, {0, 1}, {1, 0}, {1, 1} };
		for (auto& d : delta) {
			int r = pivot[0] + d[0];
			int c = pivot[1] + d[1];
			table[r * interval[0] + c] = order;
			order++;
		}
		return;
	}

	// Step 2. Slice into four space.
	int newInterval[2] = { interval[0], interval[1] / 2 };
	int newPivots[4][2] = {	{pivot[0]				, pivot[1]				},
					{pivot[0]				, pivot[1] + newInterval[1]	},
					{pivot[0] + newInterval[1]	, pivot[1]				},
					{pivot[0] + newInterval[1]	, pivot[1] + newInterval[1]	} };
	for (auto& newPivot : newPivots)
		move(table, newPivot, newInterval, order);
}

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

	cin >> N >> r >> c;

	int length = 1;
	for (int i = 0; i < N; i++)
		length *= 2;

	int* table = new int[length * length];
	int pivot[2] = { 0, 0 };
	int interval[2] = { length, length };
	int order = 0;

	move(table, pivot, interval, order);

	cout << table[r * length + c] << "\n";

	delete[] table;
	return 0;
}

이 코드를 ideone에 작성 후 stdin을 이전과 같이 지정하고 돌리면 0.03s, 134MB로 올바른 답이 출력된다.

하지만 이 코드를 백준에 제출하면 이전과 똑같이 런타임에러가 발생한다.

더 많이 알아보니, 동적할당 할 때 너무 큰 크기를 할당하면 문제가 발생하는 것 같다.

main 함수에서 table을 length * length 만큼 동적할당을 했는데, 최대 크기가 2¹⁵ * 2¹⁵ = 1,073,741,824이다.

배열을 사용하지 않고 풀어야겠다. 생각해보니, table에 값을 넣고 이를 이후에 사용하는 건 마지막 답을 출력할 때 뿐이었다. 그냥 table에 값을 넣을 때 해당 위치가 (r, c)인지를 확인 후 답을 함수 내에서 출력하면 됐다.

다음 코드는 table을 쓰지 않도록 수정한 코드 전문이다.

#include <iostream>

using namespace std;

int N, r, c;

// pivot: [r, c], interval : [2^N, K]
void move(int* pivot, int* interval, int& order) {

	// Step 0. If there is no (r, c) in this area, Stop to go on.
	if ((r < pivot[0] || r >= pivot[0] + interval[1]) && (c < pivot[1] || c >= pivot[1] + interval[1])) {
		order += interval[1] * interval[1];
		return;
	}

	// Step 1. If interval is minimum, Mark.
	if (interval[1] == 2) {
		int delta[4][2] = { {0, 0}, {0, 1}, {1, 0}, {1, 1} };
		for (auto& d : delta) {
			if (pivot[0] + d[0] == r && pivot[1] + d[1] == c) {
				cout << order << endl;
				return;
			}
			order++;
		}
		return;
	}

	// Step 2. Slice into four space.
	int newInterval[2] = { interval[0], interval[1] / 2 };
	int newPivots[4][2] = {	{pivot[0]				, pivot[1]				},
					{pivot[0]				, pivot[1] + newInterval[1]	},
					{pivot[0] + newInterval[1]	, pivot[1]				},
					{pivot[0] + newInterval[1]	, pivot[1] + newInterval[1]	} };
	for (auto& newPivot : newPivots)
		move(table, newPivot, newInterval, order);
}

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

	cin >> N >> r >> c;

	int length = 1;
	for (int i = 0; i < N; i++)
		length *= 2;

	int pivot[2] = { 0, 0 };
	int interval[2] = { length, length };
	int order = 0;

	move(pivot, interval, order);

	return 0;
}