📖Problem

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

<aside> 📌 N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

</aside>

N = 1 → $2^1\times2^1$

N = 2 → $2^2\times2^2$

N = 3 → $2^3\times2^3$

🔍Intuition

<aside> 📌 분할정복(Divide and Conquer)

</aside>

• 문제를 더 작은 문제로 나누고 각각을 재귀적으로 해결한 다음 최종적으로 전체 문제의 해결을 얻는 방식
• Z 모양의 탐색에서 재귀적으로 좌표를 쪼개는 과정이다.

🔍Approach

🚩My submission

❌1차 시도 → 시간초과

import sys
input = sys.stdin.readline

# 방문순서 구하기
def find_order_of_visit(x_start, y_start, n):
    global last

    if n > 2:
        find_order_of_visit(x_start, y_start, n//2)             # 좌측상단 : 0, 0
        find_order_of_visit(x_start, y_start + n//2, n//2)      # 우측상단 : 0, 1
        find_order_of_visit(x_start + n//2, y_start, n//2)      # 좌측하단 : 1, 0
        find_order_of_visit(x_start + n//2, y_start + n//2, n//2) # 우측하단: 1, 1
    else:
        for i in range(x_start, x_start+n):
            for j in range(y_start, y_start+n):
                last += 1
                grid[i][j] = last

N, r, c = map(int, input().split())                     # N, r행 c열
grid = [[-1 for _ in range(2**N)] for _ in range(2**N)] # 2^N * 2^N  테이블
grid[0][0] = 0
last = -1

find_order_of_visit(0, 0, 2**N)

# 정답 출력
print(grid[r][c])

시간초과가 나오는게 당연했다. 예제 5를 시도했을 때 시간이 기하급수적으로 오래 걸리는 게 체감이 되었기 때문이다.

순서만 찾으면 되는데 이를 배열에다가 하나하나 저장했던 것이 시간초과에 한 몫 한 것 같다.