1074 Z

문제

2^n * 2^n 배열을 Z방식으로 순회할 때,
M,N의 원소가 몇번째로 순회하는지 출력하는 문제이다.

Link: Z

코드

import sys
n, r, c = map(int, sys.stdin.readline().split())
cnt = 0

while(n > 0):
    mid = 2**(n-1) #중간값이지
    a,b = 0,0
    if(r < mid):
        a = 0
    else:
        a = 1
    if(c < mid):
        b = 0
    else:
        b = 1
    #print(r,c, mid)
    #print("중앙값은 : ", mid, "해당 점은 ", 2*a+b,"사분면에 있습니다", "더해지는 값은 ", (2*a+b) * mid * mid)
    cnt += (2*a+b) * mid * mid
    r -= a*mid
    c -= b*mid
    n -= 1
print(cnt)

풀이

배열을 4개의 4분면으로 나눈다고 하면
0 1
2 3 가 된다. Z 순회하는 순서와 같게 나누었다.

먼저 해당 원소가 몇 사분면에 있는지 검사한다.
그 후 cnt, r,c,n의 값을 조정한다.

cnt += (현재 사분면) * (사분면 한변의 원소의 갯수)
r,c -> mid보다 큰 값이면 mid를 뺀다.

즉 해당 사분면의 위치로 이동하는 것이므로, 값을 재조정해주는 것이다.

n = 3 일때, 8,8은 63인데
이는 3 사분면(16개 씩 봤을 때) -> 3 사분면(4개씩 봤을 때) -> 3사분면 (1개씩 봤을 때)

rc 의값은 8,8 -> 4,4 -> 1,1 이 된다.