[Python] [백준] 1074번: Z

www.acmicpc.net/problem/1074

1074번: Z

 

 

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

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

다음은 N=3일 때의 예이다.

입력

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

출력

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

 

 

 

2차원 배열을 4등분하면서 분할정복을 하면 된다.

 

import sys
input = sys.stdin.readline


def recursion(start_row, end_row, start_col, end_col, n):
    # 출력 조건
    if X == start_row and Y == start_col:
        print(n)
        return

    # 4등분하기 위한 행의 경계값
    mid_row = (start_row + end_row) // 2
    # 4등분하기 위한 열의 경계값
    mid_col = (start_col + end_col) // 2

    # 4등분된 사각형의 크기
    N = (mid_row - start_row) * (mid_col - start_col)

    # 왼쪽 위
    if start_row <= X < mid_row and start_col <= Y < mid_col:
        recursion(start_row, mid_row, start_col, mid_col, n)
    # 오른쪽 위
    elif start_row <= X < mid_row and mid_col <= Y < end_col:
        recursion(start_row, mid_row, mid_col, end_col, n + N)
    # 왼쪽 아래
    elif mid_row <= X < end_row and start_col <= Y < mid_col:
        recursion(mid_row, end_row, start_col, mid_col, n + 2 * N)
    # 오른쪽 아래
    elif mid_row <= X < end_row and mid_col <= Y < end_col:
        recursion(mid_row, end_row, mid_col, end_col, n + 3 * N)


N, X, Y = map(int, input().split())
recursion(0, 2**N, 0, 2**N, 0)