[BaekJoon] 백준 1074번 : Z

1074번 : Z

예전에 한 번 도전을 했다가 정말 어려워 풀지 못 했던 문제였다.

처음에 풀었을 때는 재귀를 이용해 풀었다. 위 예시처럼 2x2 배열이 될 때 까지 쪼갠 뒤 (r, c) 까지 쭉 가는 것 이다.

---

def visit_arr(width, i, j):
	global count

	if width == 2:
		dirs = [[0, 0], [0, 1], [1, 0], [1, 1]]
		for cur in dirs:
			if [i + cur[0], j + cur[1]] == [r, c]:
				return
			count += 1

		return

	visit_arr(width // 2, i, j)  # 좌상 시작 좌표
	visit_arr(width // 2, i, j + width // 2)  # 우상 시작 좌표
	visit_arr(width // 2, i + width // 2, j)  # 좌하 시작 좌표
	visit_arr(width // 2, i + width // 2, j + width // 2)  # 우하 시작 좌표


N, r, c = map(int, input().split())
count = 0
visit_arr(2 ** N, 0, 0)
print(count)

하지만 시간초과가 발생했다. 분명히 풀이 방법대로 풀었는데 시간초과가 나오니 너무너무 짜증났다..

다른 사람들이 올린 질문들을 봤는데 맞긴 하지만 굉장히 비효율적인 방법이었다.

내가 가고자 하는 (r, c) 이 어떤 사분면에 있는지만 안다면 나머지는 방문을 굳이 할 필요가 없다.

---

N, r, c = map(int, input().split())
count = 0

while True:
	width = 2 ** (N - 1)

	if width == 1:
		if [r, c] == [0, 1]:
			count += 1
		elif [r, c] == [1, 0]:
			count += 2
		elif [r, c] == [1, 1]:
			count += 3
		break

	if r < width <= c:  # 2사분면
		count += width ** 2
		c -= width
	elif c < width <= r:  # 3사분면
		count += width ** 2 * 2
		r -= width
	elif r >= width and c >= width:  #4사분면
		count += width ** 2 * 3
		r -= width
		c -= width

	N -= 1

print(count)

index 가지고 수학 놀이 하는 문제가 제일 어렵고 제일 짜증난다..

하지만 계속 풀어야 한다..