[BOJ / Python] 1074번: Z

문제:BOJ 1074번

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

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

풀이

뭔가 모양이 다 돌아보고 싶게 생겼다.
별찍기도 아니고 싹다 돌아다녀버렸다...

n,r,c=map(int,input().split())

n=2**n
t=-1
def z(x,y,p):
    global t
    k = p // 2

    if k==1:
        t+=1
        if x==c and y==r:
            print(t)
            exit()
        t += 1
        if x+1 == c and y == r:
            print(t)
            exit()
        t += 1
        if x == c and y+1 == r:
            print(t)
            exit()
        t += 1
        if x+1 == c and y+1 == r:
            print(t)
            exit()
    else:
        z(x,y,k)
        z(x+k,y,k)
        z(x,y+k,k)
        z(x+k,y+k,k)
z(0,0,n)

당연히 시간초과가 뜨더라. 그래서 다시 생각을 해봤는데, 무작정 순회를 하는것 보다는
4등분을 해서 몇사분면인지를 확인하는 과정을 거쳐서,

예를 들어 2사분면에 있다면, 4, 1, 3 사분면은 어차피 방문을 다 했을테니 실제로 방문을 하지 않고 총 숫자의 개수만 더해주면 될 것 같더라.

Z모양의 순서는 4사분면, 1사분면, 3사분면, 2사분면이다.

이러한 과정을 반복한다면? 답이 나오겠죵~

최종코드

import sys

n, r, c = map(int, input().split())
sys.setrecursionlimit(10 ** 9)


def z(a, x, y):
    if a == 0:
        return 0
    k = 2 ** (a - 1)
    if r < x + k and c < y + k:  # 4사분면
        return z(a - 1, x, y)
    elif r < x + k and c >= y + k:  # 1사분면
        return k * k + z(a - 1, x, y + k)
    elif r >= x + k and c < y + k:  # 3사분면
        return k * k * 2 + z(a - 1, x + k, y)
    else:  # 2사분면
        return k * k * 3 + z(a - 1, x + k, y + k)


print(z(n, 0, 0))

재귀가 쓰이는 방법이 생각보다 엄청 많은 것 같다. 항상 재귀로 풀어야지~ 생각하고 재귀로 뭐 순회를 할지.. 분할을할지.... 어쩌고 저쩌고,,, 하다가 항상 다른 방향으로 풀어서 틀리고 다시 풀어서 맞는 것 같다........ 재귀 공부 열심히 해야겠당...................................