[백준-1074] Z 파이썬 풀이

# 문제

 

# 풀이

만약 내가 찾아야하는 곳이 (7,7)의 위치면 위의 그림과 같이 된다. 주어진 정사각형은 4등분으로 구역을 나누며 Z모양을 그린다. 

이점에 주목해서 문제를 풀었다. 총 4개의 사분면으로 나누고, 현재 함수의 스택이 제 3사분면에 위치했다면, 0,1,2 사분면까지의 개수를 더해준 후, 좌표의 범위를 한단계 밑으로 축소해준다. 아래 그림을 봐보자. 문제풀면서 쓱쓱 그린거라 이쁘지는 않다..!

현재 구해야 하는 곳이 N=4, row=12, col=14라면 0~3사분면까지의 길이 + 함수(row=4,col=6)으로 다운스케일링이 가능 할 것이다. 그렇게 N=1 일때까지 함수를 호출해준다.

# 코드

import sys

def z(n,row,col):
  if n == 1:
    if row == 0 and col == 0 :
      return 0
    if row == 0 and col == 1 :
      return 1
    if row == 1 and col == 0 :
      return 2
    if row == 1 and col == 1 :
      return 3
  before_size = 2**(n-1)

  if row < before_size and col < before_size :
    count = 0
    # print(f"제 0사분면 {n}, {row}, {col}")
  elif row < before_size and col >= before_size :
    count = 1
    col -= before_size
    # print(f"제 1사분면 {n}, {row}, {col}")
  elif row >= before_size and col < before_size :
    count = 2
    row -= before_size
    # print(f"제 2사분면 {n}, {row}, {col}")
  else :
    count = 3
    row -= before_size
    col -= before_size
    # print(f"제 3사분면 {n}, {row}, {col}")
  return (count*before_size**2) + z(n-1,row,col)

def solve():
  n,row,col = map(int,sys.stdin.readline().strip().split())
  answer = z(n,row,col)
  print(answer)

if __name__ == '__main__':
    solve()

count함수는 각각의 4분면일때 몇개의 블럭인지를 계산하기 위해 사용했다.

즉 핵심 요지는, 앞에 블럭 + 함수(다운사이징 시켜 다시 조절한 좌표) 를 재귀적으로 호출 하는 풀이다.

# 마치며



재귀함수를 쓸때는 뭔가 반복적으로 일어나는 일이 있는지를 잘 찾아야 한다고 느꼈다.