https://www.acmicpc.net/problem/1074

🥚문제

---

🥚입력/출력

---

🍳코드

from sys import stdin
input = stdin.readline

# n = 2차원 배열의 크기, r = 행, c = 열
n, r, c = map(int, input().split())


# 방문 순서를 기록하기 위한 visited_id
visited_id = 0

# 함수 풀이
# (r, c)가 어느 사분면에 위치해 있는가?
# 위치한 사분면에 따라 시작하는 visited_id의 값이 달라진다
def set_visited_id(n):
    # 전역변수 선언
    global visited_id
    global r
    global c

    while n >= 1:
        if r < 2**(n-1):
            # 2사분면
            if c < 2**(n-1):
                pass

            # 1사분면
            else:
                visited_id += 2**n * 2**n // 4
                # c가 2**(n-1)보다 크다면, 다음 연산을 위하여 c값 변경
                c -= 2**(n-1)

        else:
            # r이 2**(n-1)보다 크다면, 다음 연산을 위하여 r값 변경
            r -= 2**(n-1)

            # 3사분면
            if c < 2**(n-1):
                visited_id += (2**n * 2**n // 4) * 2

            # 4사분면
            else:
                visited_id += (2**n * 2**n // 4) * 3
                # c가 2**(n-1)보다 크다면, 다음 연산을 위하여 c값 변경
                c -= 2 ** (n - 1)

        # n값 변경
        n -= 1


# 출력
set_visited_id(n)
print(visited_id)

---

🧂아이디어

• 처음에는 재귀를 이용했다

• 그러나 재귀를 이용하면 최대 2^15 * 2^15까지의 배열을 만들어야했으므로 메모리 초과였고, 이는 시간초과와도 같은 의미.

• 굳이 배열을 쓰지 않아도 구하고자 하는 좌표가 어느 사분면에 위치해있는지를 아는 것만으로도 우리는 그 좌표의 방문 순서를 구할 수 있다.

• 각 사분면의 가장 좌측 상단 좌표 ([0, 0]으로 대표될 수 있음)가 늘어나는 방식에 규칙이 있음을 파악했다.

• 2사분면 -> 1사분면 -> 3사분면 -> 4사분면 (Z 모양으로 진행)으로 갈 때 마다 2^N * 2^N // 4 만큼 더해지는 규칙을 이용하여 문제를 짧은 시간 안에 풀어낼 수 있었다.