[백준 python 1074] Z

[Silver I] Z - 1074

문제 링크

성능 요약

메모리: 31120 KB, 시간: 44 ms

분류

분할 정복, 재귀

제출 일자

2024년 2월 6일 19:35:32

문제 설명

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

N > 1인 경우, 배열을 크기가 2^N-1 × 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

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

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

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

입력

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

출력

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

풀이

n, r, c = map(int, input().split())

def zet(n, r, c):
    if n == 0:
        return 0
    half = 2 ** (n-1)
    if r < half and c < half:
        return zet(n-1, r, c)
    if r < half and c >= half:
        return half * half + zet(n-1, r, c-half)
    if r >= half and c < half:
        return 2 * half * half + zet(n-1, r-half, c)
    if r >= half and c >= half:
        return 3 * half * half + zet(n-1, r-half, c-half)

print(zet(n, r, c))

각 if문은 1, 2, 3, 4분면에 대한 구현이다.

만약 2사분면에 있는 값이면 1사분면은 다 돌았기 때문에 1사분면의 개수를 모두 받아온다.