1074 Z (python)

 

풀이방법

 

DP문제이다.

 

2차원 배열을 4등분하기

좌표 r, c가 2배가 됨에 따라 값이 4의 배수로 확장하는 규칙을 찾을 수 있음.

 

(r % 2, c % 2)로 현재 위치 (r, c)가 속한 2x2 배열에서의 상대적인 위치를 나타냄

2*(r % 2) + (c % 2)로 상대적인 위치를 기반으로 한 사분면의 인덱스를 계산

재귀적으로 이전 단계로 이동:

배열을 2^N x 2^N에서 2^(N-1) x 2^(N-1)로 줄임

int(r / 2), int(c / 2)는 현재 위치를 절반으로 나누어 새로운 위치를 계산

 

현재 위치에 대한 순서 합산:

4 * sol(N-1, int(r/2), int(c/2))는 이전 단계에서 얻은 순서를 현재 사분면 크기(4배)만큼 확장

2*(r % 2) + (c % 2)는 현재 단계에서의 상대적인 위치 순서를 더함

 

 

재귀함수 풀이

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

def sol(N, r, c):

    if N == 0:

        return 0

       

    return 2*(r%2)+(c%2) + 4*sol(N-1, int(r/2), int(c/2))

print(sol(N, r, c))

 

 

이해를 위한 예시

예시: N = 2, r = 3, c = 1이 있을 때

n = 2, 2*2 배열이고 3행 1열이면

 

이렇게 그래프가 있을 때

(0,0) (0,1) | (0,2) (0,3)
(1,0) (1,1) | (1,2) (1,3)
--------------|-------------
(2,0) (2,1) | (2,2) (2,3)
(3,0) (3,1) | (3,2) (3,3)

 

(3, 1)의 자리에 위치한다.

 

2*(3%2)+(1%2) + 4sol(2-1, int(3/2), int(1/2))에서

 

3 + 4sol(1, 1, 0)이 되고

 

다음 호출: sol(1, 1, 0)

sol (1, 1, 0) = 2

3 + 8 + s(0, 0 ,0)인데 s(0, 0, 0)은 0이므로

3 + 8 = 11로 답이 나온다.