(Python) - BOJ(1074번) : Z

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

1074번: Z

---

• 해설 : 

2^n x 2^n의 형태로 존재하는 배열을 Z모양으로 탐색하려 한다.

이 때, r행 c열을 몇 번째로 탐색하는지 찾는 문제이다.

 

---

• 풀이 :

Z모양으로 탐색하는 것을 재귀로 구현하였다. 

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래의 순으로 재귀를 호출하여 각 원소에 인덱스를 삽입하게 된다. 

r행 c열을 만난다면 그 때의 ans값을 출력한다.

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
ans = 0
 
def recursion(x,y,leng):
    global ans
    if x == r and y == c:
        print(ans)
        exit()
 
    if leng == 1:
        ans += 1
        return
 
    if not (x <= r < x + leng and y <= c < y + leng):
        ans += leng*leng
        return
 
    recursion(x,y,leng//2)
    recursion(x,y + leng // 2,leng // 2 )
    recursion(x + leng// 2 ,y, leng//2)
    recursion(x + leng//2 , y + leng //2 , leng//2)
 
 
if __name__ == '__main__':
    N,r,c = map(int,input().split())
    leng = 2**N
    recursion(0,0,leng)