[BOJ] #1074 - Z

1074번: Z

 

** 문제 유형

• 재귀 함수, 분할 정복

 

** 풀이

1. Z 모양을 구성하는 4가지 방향에 대하여 차례대로 재귀적으로 호출

 

def sol(n, r, c):
    global result

    if n == 2:
        if r == R and c == C:
            print(result)
            return
        
        result += 1
        
        if r == R and c + 1 == C:
            print(result)
            return
        
        result += 1
        
        if r + 1 == R and c == C:
            print(result)
            return
        
        result += 1
        
        if r + 1 == R and c + 1 == C:
            print(result)
            return
        
        result += 1
        return
        
    sol(n / 2, r, c)
    sol(n / 2, r, c + n / 2)
    sol(n / 2, r + n / 2, c)
    sol(n / 2, r + n / 2, c + n / 2)      

---

N, R, C = map(int, input().split(' '))

result = 0

sol(2 ** N, 0, 0)

 

-> 시간 초과

 

def divide(n, x, y):
    global result
    
    if x == r and y == c:
        print(result)
        return
    
    if x <= r < x + n and y <= c < y + n: # 찾는 위치(r, c)가 해당 범위에 포함될 경우
        divide(n//2, x, y)
        divide(n//2, x, y + n//2)
        divide(n//2, x + n//2, y)
        divide(n//2, x + n//2, y + n//2)
    else:
        result += n * n

---

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

result = 0

divide(2**n, 0, 0)

 

-> 해결