[재귀함수]★★백준 1074번 Z with Python3

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

1074번: Z

문제

 

내 풀이

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

count = 0
x = c
y = r


while N > 1:
    # 1분면
    if x < 2**(N-1) and y < 2**(N-1):
        count += 0
        N = N-1
    # 2분면
    elif x >= 2**(N-1) and y < 2**(N-1):
        count += 1 * (2**(N-1)) * (2**(N-1))
        x = x - 2**(N-1)
        N = N-1
    # 3분면
    elif x < 2**(N-1) and y >= 2**(N-1):
        count += 2 * (2**(N-1)) * (2**(N-1))
        y = y - 2**(N-1)
        N = N-1
    # 4분면
    elif x >= 2**(N-1) and y >= 2**(N-1):
        count += 3 * (2**(N-1)) * (2**(N-1))
        x = x - 2**(N-1)
        y = y - 2**(N-1)
        N = N-1
    # print(f'step{N} : {count}')

if N == 1:
    if x == 0 and y == 1:
        count += 2
    elif x == 1 and y == 0:
        count += 1
    elif x == 1 and y == 1:
        count += 3
    elif x == 0 and y == 0:
        count += 0


print(count)

재귀 함수 ver

import sys
sys.setrecursionlimit(100000)  # 최대 재귀 깊이


def dfs(x, y, N):
    global count

    if N == 1:
        if x == 0 and y == 1:
            count += 2
        elif x == 1 and y == 0:
            count += 1
        elif x == 1 and y == 1:
            count += 3
        elif x == 0 and y == 0:
            count += 0
        return

    if N > 1:
        # 1분면
        if x < 2**(N-1) and y < 2**(N-1):
            count += 0
            dfs(x, y, N-1)
    # 2분면
        elif x >= 2**(N-1) and y < 2**(N-1):
            count += 1 * (2**(N-1)) * (2**(N-1))
            dfs(x - 2**(N-1), y, N-1)

    # 3분면
        elif x < 2**(N-1) and y >= 2**(N-1):
            count += 2 * (2**(N-1)) * (2**(N-1))
            dfs(x, y - 2**(N-1), N-1)

    # 4분면
        elif x >= 2**(N-1) and y >= 2**(N-1):
            count += 3 * (2**(N-1)) * (2**(N-1))
            dfs(x - 2**(N-1), y - 2**(N-1), N-1)

    # print(f'step{N} : {count}')


if __name__ == "__main__":

    N, r, c = map(int, input().split())
    count = 0

    dfs(c, r, N)
    print(count)

 

해설

x, y 축의 반을 기준으로 4분면으로 나눠서 그 전의 pass 개수를 모두 합치고, 각좌표를 2**(N-1)의 평면으로 이동시킨다음 다시 반복했다. 

 

재귀함수로 구현할 수 있을거 같은데 아직은 못함;

08/11 성공

 

정답 풀이

풀이 개념 및 제일 정돈된 코드

https://codingcocoon.tistory.com/151

import sys

result = 0


def z(n, x, y):
    global result
    if x == r and y == c:
        print(int(result))
        exit(0)

    if n == 1:
        result += 1
        return

    if not (x <= r < x + n and y <= c < y + n):
        result += n * n
        return
    z(n / 2, x, y)
    z(n / 2, x, y + n / 2)
    z(n / 2, x + n / 2, y)
    z(n / 2, x + n / 2, y + n / 2)


n, r, c = map(int, sys.stdin.readline().split(' '))
z(2 ** n, 0, 0)

출처:https://codingcocoon.tistory.com/151

 

 

좀더 이해되는 버젼

N, X, Y= map(int, input().split())

result = 0
def solve(n, x, y):
    global result
    if n ==2:
        if x == X and y == Y:
            print(result)
            return
        result += 1
        
        if x==X and y+1 ==Y:
            print(result)
            return
        result += 1
        
        if x+1 == X and y == Y:
            print(result)
            return
        result += 1
        
        if x+1 == X and y+1 == Y:
            print(result)
            return
        result += 1
        return
    solve(n/2,x,y)
    solve(n/2, x, y+n/2)
    solve(n/2, x+n/2, y)
    solve(n/2, x+n/2, y+n/2)    
    

solve(2**N, 0,0)

출처:https://incastle-study.tistory.com/60

 

해석

재귀적으로 2*2 사이즈에 해당하는 경우의 수를 만든 다음, 그 이상 혹은 이하의 행동을 전부 귀납법적으로 해결해버렸다.

 

대단하다;;;

 

검증은 오직 if n==2 라니;