[백준/파이썬] 1074번 Z

solved.ac Class 3레벨에 속한 문제이다.

문제 주소: https://www.acmicpc.net/problem/1074

1074번: Z

문제 해석

주어진 문제의 설명과 같다.

문제 풀이

분할 정복 문제이다.

 

ㅁㅁ 1 2
ㅁㅁ 3 4
위 모양과 순서를 기준으로 숫자가 차례대로 증가하기 때문에 구하려는 행과 열이 속한 영역을 분할 정복을 통해
영역의 크기가 2 * 2가 될 때 까지 찾아준다.

찾아주는 과정에서 number += 4 ** (size - 1) 만큼의 수를 더해 빠르게 순서 계산을 해주었다.

문제 코드

number = 0
answer = -1
def z(size, x, y, r, c):
    global answer
    global number

    max_size = 2 ** (size - 1)
    if size > 1:
        if (x <= r < x + max_size) and (y <= c < y + max_size):
            z(size - 1, x, y, r, c)
        else:
            number += 4 ** (size - 1)

        if (x <= r < x + max_size) and (y + max_size <= c < y + 2 * (max_size)):
            z(size - 1, x, y + max_size, r, c)
        else:
            number += 4 ** (size - 1)

        if (x + max_size <= r < x + 2 * (max_size)) and (y <= c < y + max_size):
            z(size - 1, x + max_size, y, r, c)
        else:
            number += 4 ** (size - 1)
        if (x + max_size <= r < x + 2 * (max_size)) and (y + max_size <= c < y + 2 * (max_size)):
            z(size - 1, x + max_size, y + max_size, r, c)
        else:
            number += 4 ** (size - 1)
        
    else:
        if (x, y) == (r, c):
            answer = number
        elif (x, y + 1) == (r, c):
            answer = number + 1
        elif (x + 1, y) == (r, c):
            answer = number + 2
        elif (x + 1, y + 1) == (r, c):
            answer = number + 3
        number += 4

def solve(size, r, c):
    z(size, 0, 0, r, c)
    return answer

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

제출 결과

2 ^ 15이라 어쩌면 통과할지도 모른다는 마음으로 1씩 더해줬지만..