z [78]

Z

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

문제

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

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

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

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

생각

전체 행렬을 네 영역으로 나누는 것을 반복해서 숫자를 세는 것이 좋겠다는 생각을 하였다.

먼저 어느 사분면에 위치하는지 파악하고

그 사분면 외의 다른 부분에서의 개수를 세는 로직을 구현한다 ((2 ** N ) ** 2) * (사분면 -1)

해당하는 사분면을 또 네 영역으로 나누어 사분면 안에서의 사분면을 구하고, 이전에 센 개수와 더한다.

N을 하나씩 줄이면서 위를 계속 반복하여 N ==0 이 되면 리턴

풀이 코드

def solutuion(N, r,c):
    #탈출
    if N == 0:
        return 0
    N -=1
    result = 0
    # 1사분면
    if r <  2**N and c < 2 ** N:
        result = solutuion(N,r,c)
    # 2사분면
    elif r < 2** N :
        c -= 2**N
        result = solutuion(N,r,c) + (2**N) ** 2 * 1
    #3사분면
    elif c < 2 **N:
        r -= 2 ** N
        result = solutuion(N,r,c) + (2**N) ** 2 * 2
    #4사분면
    else:
        r -= 2 ** N
        c -= 2 ** N
        result = solutuion(N,r,c) + (2**N) ** 2 * 3
    return result

if __name__ == '__main__':
    N, r,c = map(int, input().split(" "))
    print(solutuion(N,r,c))