백준 # 1074 - Z

 

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

예제 입력 3

1 0 0

예제 출력 3

0

 

 

 

---

 

 

그림을 보아하니 일정한 규칙이 있어 특정 규칙대로 반복하면 될 것 같았다.

그런데 그 규칙을 찾는게 어려웠다는 사실...

 

 

문제에 의하면 배열은 항상 사분면을 가질 수 있다.

따라서 구하고자 하는 타깃 행/열이 어느 사분면에 위치하는지 찾아가는 방식으로 문제의 답을 구할 수 있다.

 

import sys
input = sys.stdin.readline

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

cnt = 0

while n != 0:
    n -= 1
    row = 2 ** n

    # 1사분면
    if r < row and c < row:
        cnt += 0 
    # 2사분면
    elif r < row and c >= row:
        cnt += row * row
        c -= row
    # 3사분면
    elif r >= row and c < row:
        cnt += row * row * 2
        r -= row
    # 4사분면
    else:
        cnt += row * row * 3
        r -= row
        c -= row

print(cnt)