[알고리즘] 백준 1074 파이썬 - Z

 

1074번: Z

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

 

 

문제풀이

n,r,c=map(int,input().split())
def sol(n,r,c):
	#01
    if n==0:
        return 0
    #02
    return 2*(r%2)+(c%2) + 4*sol(n-1,int(r/2),int(c/2))
#03
print(sol(n,r,c))

- #01 : n이 0이 되면 return 0을 해줄 것이다. 

           즉 아래 재귀 식을 보면 n-1이 반복되면서 0이 될 때까지 재귀를 도는 것이다.

- #02 : (0,2)=4 -> (0,4)=16 과 (1,2)=6 -> (2,4)=24 즉 r과c의 좌표가 2배가 되면 

           값은 4배가 된다. 이를 이용해서 "4*sol(n-1,int(r/2),int(c/2))"라는 재귀식을 통해

           역으로 r과 c를 2로 나누고 n은 1을 빼주며 그 값의 4배를 곱해주며,

           큰 값에서 작은 값으로 가서 최종적으로 초기값을 구하여 답을 구할 수 있다.

           참고로 모든 값은 2의 배수가 아닐 수도 있다. 그렇기에 2의 배수이면 "2*(r%2)+(c%2)"는

           0이 되어 상관없지만, 2의 배수가 아니면 r의 경우는 바로 아래 한 칸으로 이동하는데 

           값이 2가 추가되고, c는 바로 옆 한 칸으로 이동하는데 값이 1이 추가될 수 있게 조졍하였다.

- #03 : 최종적으로 return된 값을 출력해준다.