[백준] 1891번 - 사분면

📩 출처

문제

하나의 좌표평면은 다음과 같이 네 개의 사분면으로 나뉜다.

그러면, 각각의 사분면을 다시 사분면으로 나누어 번호를 붙여 보면 어떨까? 예를 들어 1번 사분면의 1번 사분면은 11번 사분면, 3번 사분면의 2번 사분면은 32번 사분면이라고 하면 좋지 않을까? 물론 한 번 더 나눠 볼 수도 있겠다. 3번 사분면의 4번 사분면의 1번 사분면은 341번 사분면이다.

사분면의 번호 길이가 길어짐에 따라 각각의 사분면의 크기는 급격히 작아지며, 그 개수는 기하급수적으로 증가한다.

사분면에 번호를 붙이는 이러한 규칙을 상정하고서, 어떤 사분면 조각을 이동시켰을 때, 그 조각이 위치하게 되는 사분면의 번호가 궁금하다. 예를 들어, 341번 사분면을 오른쪽으로 두 번, 위쪽으로 한 번 이동시키면 424번 사분면에 온다.

하나의 사분면 조각을 이동시켰을 때, 그 조각이 도착한 사분면의 번호를 알아내는 프로그램을 작성하라.

입력

첫 줄에 이동시키려는 사분면 조각 번호의 자릿수를 나타내는 정수 d와, 그 사분면 조각의 번호가 주어진다. (1 ≤ d ≤ 50) 둘째 줄에는 이동의 내용을 나타내는 두 정수가 x, y가 주어진다. (|x|, |y| ≤ 250) 오른쪽으로 이동한 경우 x가 양수, 왼쪽으로 이동한 경우 음수이며, 그 절댓값은 오른쪽 왼쪽 방향 이동 횟수를 나타낸다. 위쪽으로 이동한 경우 y가 양수, 아래쪽으로 이동한 경우 음수이며, 역시 그 절댓값은 아래위 방향 이동 횟수를 나타낸다.

출력

첫 줄에 도착한 사분면의 번호를 출력한다. 만약, 존재하지 않는 사분면인 경우에는 -1을 출력한다.

👉 생각

• 먼저 주어지는 사분면 조각 번호의 위치를 찾는다. 좌표명면을 직접 만들지는 않지만 범위를 축소하면서 위치를 찾아 갈 수 있는데, 각 i와 j의 초기 범위는 0 <= i < 2**d, 0 <= j < 2**d이다. 이 좌표를 4분면으로 축소하면 위치를 찾을 수 있다.
• 찾은 위치에 각각 y와 x를 더해주면 찾고자 하는 값의 위치가 나오는데 이 좌표를 check라는 함수를 통해서 좌표가 속한 범위를 축소해나간다. 한번 축소할 때마다 해당 사분면의 값을 answer에 더해준다.
• answer의 길이가 d와 같을 때 answer를 반환해준다.

def find(n1, n2, m1, m2, idx):
   if idx == len(number):
       return n1, m1

   if number[idx] == '1':
       return find(n1, (n1+n2)//2, (m1+m2)//2, m2, idx+1)
   elif number[idx] == '2':
       return find(n1, (n1+n2)//2, m1, (m1+m2)//2, idx+1)
   elif number[idx] == '3':
       return find((n1+n2)//2, n2, m1, (m1+m2)//2, idx+1)
   elif number[idx] == '4':
       return find((n1+n2)//2, n2, (m1+m2)//2, m2, idx+1)

def check(n1, n2, m1, m2):
    global answer
    if len(answer) == int(d):
        return answer

    if n1 <= nx < (n1+n2)//2 and (m1+m2)//2 <= ny < m2:
        answer += '1'
        return check(n1, (n1 + n2) // 2, (m1 + m2) // 2, m2)

    elif n1 <= nx < (n1+n2)//2 and m1 <= ny < (m1+m2)//2:
        answer += '2'
        return check(n1, (n1 + n2) // 2, m1, (m1 + m2) // 2)

    elif (n1+n2)//2 <= nx < n2 and m1 <= ny < (m1+m2)//2:
        answer += '3'
        return check((n1 + n2) // 2, n2, m1, (m1 + m2) // 2)

    elif (n1+n2)//2 <= nx < n2 and (m1+m2)//2 <= ny < m2:
        answer += '4'
        return check((n1 + n2) // 2, n2, (m1 + m2) // 2, m2)

d, number = input().split()
x, y = map(int, input().split())

n, m = 2**int(d), 2**int(d)

dx, dy = find(0, n, 0, m, 0) # 사분면 조각의 좌표
nx, ny = (-1*y) + dx, x + dy # 새로운 사분면 조각의 좌표
answer = ''

if 0 <= nx < n and 0 <= ny < m:
    print(int(check(0, n, 0, m)))
else:
    print(-1)