[백준] 1074번 Z - C++

---

Z

 위 그림과 같이 주어진 보드를 z모양으로 순회할 때 r행 c열에는 몇 번째로 방문하는지 출력하는 문제입니다. 행, 열 번호와 방문 순서는 모두 0부터 시작합니다.

---

입력

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

출력

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

제한

• 1 <= N <= 15
• 0 <= r, c < 2^N

예제 입력

2 3 1

예제 출력

11

---

풀이 방법

1. 현재 보드를 좌상단의 좌표x, y와 보드의 size로 표현한다. size=2^z

2. count = 0

3. 현재 보드에서 c, r의 위치가 좌상단, 좌하단, 우상단, 우하단 중 어디인지 알아낸다.

4. n>1일 경우, 위치에 따라 count변수에 0, size*size/2, size*size/4, size*size/4*3을 더한다.

5. n=1일 경우, 위치에 따라 count변수에 0, 2, 1, 3을 더한다.

6. z를 1 감소시키고 z==0이 될 때까지 반복한다.

7. count를 출력한다.

코드

#include <iostream>

using namespace std;

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

	int n, r, c;
	cin >> n >> r >> c;

	int x = 0, y = 0, z = n, count = 0;
	while (z > 0)
	{
		int size = pow(2, z);
		int midX = x + size / 2;
		int midY = y + size / 2;
		if (z > 1)
		{
			if (c < midX)
			{
				// 좌상단
				if (r < midY)
				{

				}
				// 좌하단
				else
				{
					count += size * size / 2;
					y = midY;
				}
			}
			else
			{
				// 우상단
				if (r < midY)
				{
					count += size * size / 4;
					x = midX;
				}
				// 우하단
				else
				{
					count += size * size / 4 * 3;
					x = midX;
					y = midY;
				}
			}
		}
		else if (z == 1)
		{
			if (c == x)
			{
				if (r != y)
					count += 2;
			}
			else
			{
				if (r == y)
					count += 1;
				else
					count += 3;
			}
		}
		--z;
	}
	cout << count;
	return 0;
}

마치며

 처음으로 골드단계의 문제를 해결했습니다. 이전에 학교 수업을 통해 플래티넘 단계의 문제를 해결한 적은 있지만 자력으로 골드이상의 문제를 푼 것은 오늘이 처음이네요. 사실 막연한 두려움 때문에 골드단계에 도전하지 못하고 있었는데 이번에 용기를 얻었습니다. 어려워 보여도 모두들 도전하시길 바랍니다. 파이팅! ^^