백준 1074번 Z

https://www.acmicpc.net/problem/1074
실패이유: 구현실패

def split(n, x, y):
    if n == 1:
        return 2 * y + x

    else:
        if x < 2 ** (n - 1):
            if y < 2 ** (n - 1):                                                # 왼쪽 위, 분할된 정사각형에 위치
                return split(n - 1, x, y)
            else:                                                               # 왼쪽 아래, 분할된 정사각형에 위치
                return split(n - 1, x, y - (2 ** (n - 1))) + 2 ** (2 * n - 2) * 2                   # 분할된 정사각형 2개가 뒤에 있다.
        else:
            if y < 2 ** (n - 1):                                                # 오른쪽 위, 분할된 정사각형에 위치
                return split(n - 1, x - (2 ** (n - 1)), y) + 2 ** (2 * n - 2)                          # 분할된 정사각형 1개가 뒤에 있다.
            else:                                                               # 오른쪽 아래, 분할된 정사각형에 위치
                return split(n - 1, x - (2 ** (n - 1)), y - (2 ** (n - 1))) + 2 ** (2 * n - 2) * 3  # 분할된 정사각형 3개가 뒤에 있다.


n, y, x = map(int, input().split())
print(split(n, x, y))

• 만약 (2, 5) 위치의 방문순서를 계산하고자 한다면
  
  
• 해당 위치가 왼쪽 아래임을 x < 2 ** (n - 1), y > 2 ** (n - 1) 을 통해 알 수 있다.
  • 현재 n = 3
    
    
    
• 그렇다면 현재 이전 부분의 개수를 덩어리로 셀 수 있다.
  • 하늘색 분할된 정사각형의 한 개는 총 2^(n-1) * 2^(n-1) = 2^(2n - 2) 개수를 갖는다.
    
    
    
• 이후 x 좌표는 그대로, y좌표는 분할된 정사각형 길이만큼 빼준뒤 다시 분할 과정을 반복한다.
  • x -> x -> 2
  • y -> y - (2 ** (n - 1))) -> 5 - 4 -> 1
    
    
• 이렇게 재귀적인 동작을 통해 정답을 구할 수 있다.

출처: 코드플러스 - 알고리즘 중급 1/3 강의
https://code.plus/course/43