[파이썬/Python] 백준 1074번 Z

[파이썬/Python] 백준 1074번 Z

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열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

예제 입력

2 3 1

예제 출력

11

해설

배열을 사분면으로 나눠서, 해당 row, col 이 어디에 해당하는지 탐색하는 방법으로 접근하면 쉽게 풀 수 있다.

예제 입력을 3 7 7 이라 해보자.

array[7][7] 은 8*8 배열에서 4사분면에 포함되어 있다.

그럼 4사분면을 다시 분할해보자.

array[7][7] 은 4*4 배열에서 4사분면에 포함되어 있다.

또 다시 4사분면을 분할해보자.

array[7][7] 은 2*2 배열에서 4사분면에 포함되어 있다.

더 이상 분할할 수 없으므로, 답은 63이다.

풀이

분할정복 알고리즘

import sys
input = sys.stdin.readline

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

res = 0
l = 2 ** (n-1) # 한 사분면의 길이

# 길이가 0이 되면 종료
while l: 
    if c // l < 1:
        if r // l >= 1: # 3사분면
            res += 2 * l * l
    else:
        if r // l < 1: # 1사분면
            res += l * l
        else: # 4사분면
            res += 3 * l * l
    # 해당하는 구역을 다시 분할
    c %= l
    r %= l
    l //= 2

print(res)

주어진 코드의 시간 복잡도를 분석해보자.

주요 반복문은 while l: 부분이다. l은 입력으로 주어진 n에 따라 초기화되며, l은 입력 크기에 비례하므로 O(log n)이다.

반복문 내에서 수행되는 연산은 상수 시간에 수행된다. 각각의 조건문과 연산은 모두 O(1) 시간이 걸린다.

따라서 전체적인 시간 복잡도는 O(log n)이다.