less than 1 minute read

문제

접근 방법

패턴이 반복된다는 것에서 전체적인 규칙을 발견하려고 했는데 내 머리로는 불가능함을 알았다.

더 효율적인 방법은 2x2에서의 Z 패턴은 확실하게 알기 때문에 전체를 2x2가 될 때까지 분할하여 재귀로 풀면 된다. 4x4를 보면 1,2,3,4 사분면으로 동일한 패턴이 나타나고 8x8을 봐도 1,2,3,4 사분면으로 동일한 패턴이 반복됨을 알 수 있다.

이 정보를 통해 사분면별로 나눠서 2x2가 되도록 분할하면 된다고 생각했다. 각 사분면의 시작되는 지점의 값을 보면 4x4에서는 0,4,8,12이고 8x8에서는 0,16,32,48이라는 것을 통해 더 작은 영역으로 분할을 할 때 이 시작값들을 더해주어 값에 영향이 없도록 하였다.

정답 코드


import sys
input = sys.stdin.readline



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


def func(n,r,c):
  if n==1:
    if r==0 and c==0:
      return 0
    elif r==1 and c==0:
      return 2
    elif r==0 and c==1:
      return 1
    else:
      return 3
    
  #첫 사분면일 때:
  elif r<2**(n-1) and c<2**(n-1):
    return func(n-1, r, c)

  #두번째 사분면일 때:
  elif r<2**(n-1) and c>=2**(n-1):
    return (2**(n-1))**2 + func(n-1, r, c-2**(n-1))

  #세번째 사분면일 때:
  elif r>=2**(n-1) and c<2**(n-1):
    return 2*(2**(n-1))**2 + func(n-1, r-2**(n-1), c)

  #네번째 사분면일 때:
  else:
    return 3*(2**(n-1))**2 + func(n-1, r-2**(n-1), c-2**(n-1))
  
print(func(n,r,c))

You May Also Enjoy