[Python Silver I 1076] Z

https://www.acmicpc.net/problem/1074

1074번: Z

시간 제한	메모리 제한
0.5초	512MB

 

문제

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

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

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

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

 

입력

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

 

출력

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

 

알고리즘 분류

• 분할 정복
• 재귀

---

 📖 Code

N, x, y = map(int, input().split())
result = 0

def z(n):
    global x,y,result
    num = 2**(n-1)
    if num <= x and num <= y: 
        result += (3 * num**2)
        x-= 2**(n-1)
        y-= 2**(n-1)
        return z(n-1)
    elif num <= x:
        result += (2 * num**2)
        x-= 2**(n-1)
        return z(n-1)
    elif num <= y:
        result += (1 * num**2)
        y-= 2**(n-1)
        return z(n-1)
    else:
        if (x==0 and y==0) or (x==1 and y==0) or (x==0 and y==1) or (x==1 and y==1):
            if x==0 and y==0:
                return print(result)
            elif x==0 and y==1:
                return print(result+1)
            elif x==1 and y==0:
                return print(result+2)
            else:
                return print(result+3)
        
        return z(n-1)
    
z(N)

 ✅ Comment

이 문제는 일일이 찾는다면 구현하기는 쉽지만?

시간제한 때문에 일일이 찾을 수 없다.



이문제는 딱 보면 2*2 크기의 배열 4*4 크기의 배열 8*8... 배열들이 반복되는 구조이다.

반복되기떄문에 처음에 주어지는 배열의 크기 N을 기준으로 

N-1... N-2... 이런 식으로 4등분하여 주어진 좌표값이 몇번째 숫자인지 알아내면 쉽게 풀 수 있다.