1074번 Z - Python

문제

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

풀이

분할 정복으로 2by2까지 자른다음에 하나하나 찾아보는 식으로 문제를 풀었는데, 시간초과가 났다. 문제를 어떻게 풀까 고민하다가 r, c가 포함된 구간만 분할정복으로 나누면 되지 않을까 했다.
r, c가 포함된 사분면으로 계속 나누면서 count를 증가하면 된다. 여기서 count를 분할할 사분면에 맞게 추가해줘야 하는데, 1사분면을 분할 한다는 것은 2사분면에 r, c가 맞지 않다는 것이니 2사분면 만큼을 count해주어야 한다.

코드

from sys import stdin

input = stdin.readline

def z(x, y, n):
    global count
    if n==2: #(2,2)안에 r, c가 있다면 찾은 뒤 출력한다.
        for i in range(y,y+2):
            for j in range(x,x+2):
                if i==r and j==c:
                    print(count)
                    exit(0)
                count+=1

    else:
        next = n//2
        if y<=r<y+(next) and x<=c<x+(next):     #2사분면
            z(x,y,next)
        elif y<=r<y+(next) and x+(next)<=c<x+n: #1사분면
            count += next*next #2사분면을 건너뛴거니 그 만큼 더해준다.
            z(x+(next),y,next)
        elif y+(next)<=r<y+n and x<=c<x+(next): #3사분면
            count += next*next*2 #1,2사분면을 건너뛴거니 그 만큼 더해준다.
            z(x,y+(next),next)
        else:                                   #4사분면
            count += next*next*3 #1,2,3사분면을 건너뛴거니 그 만큼 더해준다.
            z(x+(next),y+(next),next)

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

count = 0
z(0,0,2**n)

다른 코드

반복문의 형식으로 푸는 방법도 있다. / 나눈 곳을 데려오는 방식이다.

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

ans = 0

while N != 0:

	N -= 1

	# 2사분면
	if r < 2 ** N and c < 2 ** N:
		ans += ( 2 ** N ) * ( 2 ** N ) * 0

	# 1사분면
	elif r < 2 ** N and c >= 2 ** N: 
		ans += ( 2 ** N ) * ( 2 ** N ) * 1
		c -= ( 2 ** N )
        
	# 3사분면    
	elif r >= 2 ** N and c < 2 ** N: 
		ans += ( 2 ** N ) * ( 2 ** N ) * 2
		r -= ( 2 ** N )
        
	# 4사분면    
	else:
		ans += ( 2 ** N ) * ( 2 ** N ) * 3
		r -= ( 2 ** N )
		c -= ( 2 ** N )
    
print(ans)

참고

ggasoon2 / 다양한 풀이를 알 수 있다.
siyamaki / 경계값 처리에 도움을 주셨다.