[백준 파이썬] 1074 Z

📌문제 출처

솔브닷 class 3+ 단계
https://www.acmicpc.net/problem/1074

1074번: Z

❓ 문제

)

)

❗ 풀이

• 재귀, 분할 정복

📗 풀이 코드

import sys
input = sys.stdin.readline

def zearch(n,r,c):
    if n==0:
        return 0
    nr,rr = divmod(r,2)
    nc,rc = divmod(c,2)
    return 2*rr + rc + 4*zearch(n-1,nr,nc)
n,r,c = map(int,input().split())
print(zearch(n,r,c))

📗 코드 해설

• 전체 범위가 2**15이므로 모든 배열을 그린 뒤에 연산하는 것은 시간초과날 것이 뻔하다.
• 아래와 같이 재귀함수를 사용할 수 있는 규칙을 발견할 수 있다.
  
• 노란색 (6,4)는 56이고, 노란색 (3,2)는 14이다.
  파란색(6,6)은 60이고, 파란색 (3,3)은 15다.
  분홍색 (2,2)는 12고, (1,1)은 3이다.
• 위처럼 행과 열이 각각 반이 되면 값은 1/4이 되는 규칙이 있다.
  가장 작은 단위의 사각형은 네개의 숫자가 연속으로 되어있기에
  문제에서 주어진 행과 열을 네개 사각형의 꼭지점으로 이동한 후 각 행과 열을 1/2씩 해주기를 반복하면
  모든 배열을 그리지 않고도 빠르게 답을 찾을 수 있다.
• 먼저 기본 단위 사각형의 꼭지점으로 이동하기 위해 행과 열을 모두 자신보다 작은 최초의 짝수로 이동시킨다.
  이때 홀수라면 1을, 짝수라면 0을 빼주면 되기에 새로운 행, 열인 nr, nc = r//2, c//2 가 된다.
• 이때 나머지는 기본 단위 사각형 꼭지점으로 이동하는 횟수가 되며 열이동은 2, 행이동은 1 차이가 나므로
  열이동 횟수에 2를 곱하여 더해줄 것이다.
• 꼭지점 이동이 1/2씩 되기에, n은 1씩 줄어드는 순서로 재귀함수를 탑다운으로 진행한다.
  n == 0 일때는 모든 꼭지점이 (0,0)으로 수렴하므로 이때 0을 반환해준다.