백준 1074번: Z

✔ 풀이를 위한 아이디어

• 분할 정복 (Divide and Conquer)
• 재귀 (Recursion)
  
  

✔ 수정 전 코드 [시간 초과]

import sys

count = -1

def traverse(start_x, start_y, n):
    global count
    if n == 1:
        count += 1
        if start_x == c and start_y == r:
            print(count)
    else:
        traverse(start_x, start_y, n//2)
        traverse(start_x + n//2, start_y, n//2)
        traverse(start_x, start_y + n//2, n//2)
        traverse(start_x + n//2, start_y + n//2, n//2)


N, r, c = map(int, sys.stdin.readline().split())
traverse(0, 0, 2**N)

• 사실 색종이 만들기 문제를 풀고 나면 쉽게 아이디어를 떠올릴 수 있다. 그래서 기분좋게 코드를 짜서 제출했더니 시간 초과가 나버렸다.
• Z 순서대로 순회하는 것은 결국, 재귀적으로 1, 2, 3, 4 사분면 순서대로 순회하는 것을 의미하므로 위와 같이 코드를 짜면 된다.
• count 값만 계속 올려주면서 순회를 진행하다가, 원하는 행과 열의 값에 도달하게 되면 현재의 count 값을 출력하는 방식이다.
  
  

✔ 수정 후 코드

import sys

count = -1

def traverse(start_x, start_y, n):
    global count
    if n == 1:
        count += 1
        if start_x == c and start_y == r:
            print(count)
    else:
        if c < start_x + n//2 and r < start_y + n//2: #1사분면
            traverse(start_x, start_y, n//2)
        else:
            count += (n//2)**2
        if c >= start_x + n//2 and r < start_y + n//2: #2사분면
            traverse(start_x + n//2, start_y, n//2)
        else:
            count += (n//2)**2
        if c < start_x + n//2 and r >= start_y + n//2: #3사분면
            traverse(start_x, start_y + n//2, n//2)
        else:
            count += (n//2)**2
        if c >= start_x + n//2 and r >= start_y + n//2: #4사분면
            traverse(start_x + n//2, start_y + n//2, n//2)
        else: #사실 이 else문은 지워도 무방하다.
            count += (n//2)**2


N, r, c = map(int, sys.stdin.readline().split())
traverse(0, 0, 2**N)

• 시간 초과를 방지하기 위해서는 전부 탐색하지 않고, 문제에서 요구한 행과 열을 포함하는 사분면으로만 탐색을 진행하면 된다.
• 따라서 위처럼 케이스를 나누어 찾는 값이 없는 사분면은 직접 순회하는 대신 count 값만을 올려주는 것으로 대신하였다.
  
  

✔ 관련 개념

• 분할 정복 (Divide and Conquer) 과 재귀 (Recursion)