[백준 1074번] Z (Python/파이썬)

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

1074번: Z

분할정복 알고리즘으로 Z(2X2)모양이 나올때까지 좌표를 분할하여 Z가 되면 탐색을 하였다.

처음에는 좌표를 2차원 배열로 만들어서 직접 분할하였다. 숫자를 다 쓰면서 해당 좌표가 (r,c)이면 프로그램을 종료하게 했지만 시간초과가 떴다.

그래서 좌표를 분할할때 분할한 범위 안에 (r,c)가 없으면 탐색을 아에 하지 않도록 return을 추가해주었다.

하지만 그래도 시간초과가 떠서...다시 코드를 보니 굳이 2차원 배열을 만들 필요가 없었다.

배열에 직접 표기하지 않고, 규칙에 따라 숫자만 더해주면 되므로 배열에 숫자를 표기하는건 불필요한 과정이었다.

그래서 배열을 없앴더니 바로 통과되었다.

시도는 6번이나 했지만 쓸데 없는 시도가 많아서 수정하는데 까지는 얼마 안걸렸다.

(보니까 2차원 배열 설정에서 시간복잡도가 많이 터진거 같다...ㅋㅋ)

코드는 다음과 같다.

 

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N, r, c = map(int,input().split())
N = 2**N
num = 0

def divide(x,y,n):
  global num
  ## 범위를 벗어난 곳은 분할 안함
  if x > r or y > c or x+n<=r or y+n<=c:
    num += n**2
    return
    
  ## (r,c)가 포함된 들어간 2X2 좌표탐색
  if n == 2:
    for i in range(x,x+2):
      for j in range(y,y+2):
        if i == r and j == c:
          print(num)
          sys.exit()
        num += 1
  ## 분할
  else:
    divide(x,y,n//2)
    divide(x,y+n//2,n//2)
    divide(x+n//2,y,n//2)
    divide(x+n//2,y+n//2,n//2)

divide(0,0,N)

 

 

 

 

 

 

 

 

그닥 어렵지 않은 문젠데 2차원배열로 쓸데없이 숫자를 입력해서 시간복잡도가 터졌다, 한번에 못맞춰서 아쉽다