PS/백준

실버1 z(1074)

jjw000628 2023. 12. 31. 23:27
 

1074번: Z

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

www.acmicpc.net

위의 문제를 보고 분할 정복 문제라는 것을 알았지만, 분할 정복를 정확하게 모르고 있었기에 풀어내는데 조금 오래 걸렸다. 

import sys
input = sys.stdin.readline

def printResult(value, location):
  print(value + location)
  exit(0)

def divide(n, r, c, value):
  n //= 2
  if r < n and c < n:
    if n == 1: printResult(value, 0)
    divide(n, r, c, value)
  elif r < n and c >= n:
    if n == 1: printResult(value, 1)
    divide(n, r, c-n, value + (n**2 * 1))
  elif r >= n and c < n:
    if n == 1: printResult(value, 2)
    divide(n, r-n, c, value + (n**2 * 2))
  else:
    if n == 1: printResult(value, 3)
    divide(n, r-n, c-n, value + (n**2 * 3))

n, r, c = map(int,input().split())
divide(2**n,r,c,0)

입력 받은 n, r, c를 이용해서 각 사분면에 해당하면 재귀를 할 수 있게 만들었다. 이 문제는 정말 그림을 그려서 각 사분면의 숫자의 규칙성을 알아내는 것이 가장 중요했다. 그 규칙성을 빨리 찾았다면 수월하게 구현할 수 있었을 것이다.