[백준][재귀] 1074 - Z

문제

https://www.acmicpc.net/problem/1074

1074번: Z

 

코드

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

def z(n, x, y):
  global result
  if n == 2:
    if x == r and y == c:
      print(result)
      return
    result += 1
    if x == r and y+1 == c:
      print(result)
      return
    result += 1
    if x+1 == r and y == c:
      print(result)
      return
    result += 1
    if x+1 == r and y+1 == c:
      print(result)
      return
    result += 1
    return
  z(n / 2, x, y)
  z(n / 2, x, y+(n/2))
  z(n / 2, x+(n/2), y)
  z(n / 2, x+(n/2), y+(n/2))

result = 0
z(2**N, 0, 0)

결과가 잘 나오지만 분할 정복 알고리즘을 사용 시 더 개선할 수 있다.

 

분할 정복 알고리즘이 적용된 코드

def z(n, x, y):
  if n == 1:
    return 2 * x + y
  half = 2 ** (n - 1)
  if x < half and y < half:
    return z(n - 1, x, y)
  elif x < half and y >= half:
    return (half ** 2) + z(n - 1, x, y - half)
  elif x >= half and y < half:
    return (half ** 2) * 2 + z(n - 1, x - half, y)
  else:
    return (half ** 2) * 3 + z(n - 1, x - half, y - half)

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

위 경우에선 모든 좌표에 대해 체크하며 r, c와 맞아 떨어지는 값을 구하지만

구역에 대한 depth가 내려올 때 해당하는 위치에 대해 특정 값을 더해 구하는 규칙을 통해

r, c의 값에 대해 건너뛰어가며 답을 찾아내기 때문에 재귀 호출 횟수 자체가 훨씬 적어지게 된다.

 

예로 3 7 7에 대한 입력 시 처음 코드는 46번의 재귀 호출이 발생하지만

분할 정복 알고리즘이 적용된 코드는 20번만 호출한다.