[BOJ/백준] 1074 Z - 파이썬

문제

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

1074번: Z

 

 

 

문제풀이

재귀를 사용해서 푸는 문제이다.

처음 (2^N)*(2^N) 크기의 2차원 배열에서부터 4사분면으로 나누어 길이를 반씩 줄여나간다.

분할된 네 공간 중 ( r , c )가 어느 곳에 속하는지 확인한다.

속하지 않는 부분에 대해서는 그 크기만큼 ans 값을 더해준다.

x==r 이고 y==c 이면 ans를 출력하고 종료한다.

 

코드

import sys
input=sys.stdin.readline

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

def solve(x,y,n): #x,y시작점, 각 내부사각형
    global ans
    if x==r and y==c:
        print(ans)
        exit(0)
    if n==1:
        ans+=1
        return
    if not (x<=r<x+n and y<=c<y+n):
        ans+=n*n
        return
    temp=n//2
    solve(x,y,temp)
    solve(x,y+temp,temp)
    solve(x+temp,y,temp)
    solve(x+temp,y+temp,temp)

solve(0,0,2**n)
print(ans)

 

기타

구현 자체는 그다지 어려운 문제는 아니었으나, 처음에 재귀가 아니라 for문으로 직접 다 돌리려고 시도했어서 시간이 좀 걸렸다.

x가 r이고 y가 c일 때, 바로 출력하지 않고 return을 해주었었는데 solve()에서 4개의 solve()가 또 새로 돌아가기 때문에 바로 출력 후 종료해주어야 한다.