[백준][Python] 1074 Z

대표 분할정복이자 재귀문제.

 

재귀는 3가지가 중요하다.

1. 매개변수(n일때)

2. 최종 계산할 요소(n==0,n==1등 최소 분할 단위)

3. 재귀인자 주입(n-1일때, n+1일때. 각 매개변수의 변동 등.)

import sys
input = sys.stdin.readline

# 핵심은 배열을 4등분하는 분할을 통해 
# 배열의 크기가 1인 사각형들의 모임으로 만드는 것. 
def Z(n,r,c):
    # 배열의 크기가 1이 되면 0을 정복하여 반환한다.
    if n==0: 
        return 0
    # 배열의 크기를 반을 기준으로 4영역으로 분할한다.
    harf = 2**(n-1)
    if r < harf and c<harf: 
        return Z(n-1,r,c)
    elif r < harf and c>=harf: 
        return harf**2 + Z(n-1,r,c-harf)
    elif r >=harf and c<harf: 
        return 2*harf**2 + Z(n-1,r-harf,c)
    else:
        return 3*harf**2 + Z(n-1,r-harf,c-harf)

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