[백준🥈1] #1074 Z (Python)

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

제한

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

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

예제 입력 3

1 0 0

예제 출력 3

0

예제 입력 4

4 7 7

예제 출력 4

63

예제 입력 5

10 511 511

예제 출력 5

262143

예제 입력 6

10 512 512

예제 출력 6

786432

❌ Code (시간초과)

import sys
input = sys.stdin.readline

n, r, c = map(int, input().split())
cnt, flag = 0, 0
def z(x, y, n):
    global cnt
    global flag

    if flag == 1:
        return

    if x == r and y == c:
        print(cnt)
        flag = 1
        return

    for _ in range(x, x+n):
        for _ in range(y, y+n):
            if n > 1:
                z(x, y, n//2)
                z(x, y+n//2, n//2)
                z(x+n//2, y, n//2)
                z(x+n//2, y+n//2, n//2)
                return

    cnt += 1

z(0, 0, 2**n)

일반 분할정복 문제라 생각하고 풀었다. 시간제한이 0.5초에 최대 범위가 2^30이 되는데 1칸이 될 때 까지 다 쪼개고 있으니.. 시간초과가 안 날 수가 없다... ㅎ...

✔️ Code

import sys
input = sys.stdin.readline

def z(x, y, n):
    global cnt

    if x > r or x+n <= r or y > c or y+n <= c:
        cnt += n**2
        return

    if n > 2:
        z(x, y, n//2)
        z(x, y+n//2, n//2)
        z(x+n//2, y, n//2)
        z(x+n//2, y+n//2, n//2)
    
    else:
        if x == r and y == c:
            print(cnt)
        elif x == r and y+1 == c:
            print(cnt+1)
        elif x+1 == r and y == c:
            print(cnt+2)
        else:
            print(cnt+3)
        sys.exit()

n, r, c = map(int, input().split())
cnt = 0
z(0, 0, 2**n)

✏️ Comment

포인트는 다 분할탐색 하는 것이 아니라 시작 지점부터 한 변의 길이를 더한 지점까지 r행 c열이 포함되어 있을 경우에만 분할탐색을 하고, 그렇지 않은 부분은 변의 제곱을 개수에 더해주는 것이다.

해당 범위에 r행 c열이 있을동안 계속 분할탐색하다가 2*2의 정사각형이 남았을 때 (Z를 만들 수 있는 4칸) 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 좌표를 각각 확인해서 개수를 더해준다.

이틀 뒤에 다시 풀어보는 걸로 ㅎ