본문 바로가기
코딩/백준

알고리즘 - Python / 백준 - 1074번 : Z

반응형

1074번: Z (acmicpc.net)

 

1074번: Z

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

www.acmicpc.net

 


 

풀이

  • 2^N * 2^N 쿠기의 배열을 Z모양으로 탐색한다.
  • 한번에 정사각형 모양으로 탐색하므로 쪼갤 수 있는 가장 작은 단위까지 쪼개면서 세면된다.
  • 4등분을 한 후 , 등분에 따라 0 , SIZE * 1/4 , SIZE * 2/4 , SIZE * 3/4 의 인덱스로 쪼개고 각각을 더해가면서 몇번째로 탐색하는지 알아낼 수 있다.
  • 문제의 예제인 2 3 1 의 경우 , 처음 쪼갤때는 SIZE * 2/4 인 조각에 속하고 , 이후에는 0 , 1 , 2 , 3 중 3에 속하므로 SIZE * 2/4 ( 8 ) + 3 = 11 번째 탐색되는 경우이다. 

 

import sys

n,r,c= map(int, sys.stdin.readline().split())

def check(r,c,n):
  size = (2**n)**2
  block = int(size/4)
  ans = 0
  move = 2**(n-1)
  if n == 1:
    if r==0 and c==0:
      return 0
    elif r==0 and c==1:
      return 1
    elif r==1 and c==0:
      return 2
    elif r==1 and c==1:
      return 3
  else:
    if r<(2**(n-1)):
      if c<(2**(n-1)):
        ans += 0
        ans += check(r,c,n-1)
      else:
        ans += block
        ans += check(r,c-move,n-1)
    else:
      if c<(2**(n-1)):
        ans += (2*block)
        ans += check(r-move,c,n-1)
      else:
        ans += (3*block)
        ans += check(r-move,c-move,n-1)
  return ans

print(check(r,c,n))

 

 

반응형