문제
한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다.
예를 들어, 2×2 배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N > 1인 경우, 배열을 크기가 2^{N-1} × 2^{N-1}로 4등분 한 후에 재귀적으로 순서대로 방문한다.
다음 예는 2^2 × 2^2 크기의 배열을 방문한 순서이다.
다음은 N=3일 때의 예이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성.
입력
첫째 줄에 정수 N, r, c가 주어진다.
출력
r행 c열을 몇 번째로 방문했는지 출력한다.
아이디어
Z의 규칙
-
2 \times 2 크기의 Z는 4개 칸을 가지고 만든다. 각 Z가 시작되는 숫자를 보자.
→ 4의 배수를 따른다. 0, 4, 8, 12, 16, 20, …
-
4 \times 4 크기의 Z는 16을 기준으로 만든다. 각 Z가 시작되는 숫자를 보자.
→ 16의 배수를 따른다. 0, 16, 32, 48, …
-
n \times n 크기의 Z는 n^2를 기준으로 만든다.
따라서 Z가 시작되는 숫자와 n을 기준으로 판단한다.
함수 만들기
큰 박스와 작은 박스가 있다고 생각하자. 작은 박스 4개로 큰 박스를 만든다.
먼저, 번호를 담는 변수(cnt)를 함수 밖에 만든다. (전역변수로)
- 박스 안에 있는지 확인
- x < r < x+n 이고, y < r < y + n 인지 보기.
- 맞다면 계속 진행
- 아니면 n을 2배해주기. (박스의 크기를 키운다.)
- 큰 박스 → 작은 박스로 나눠 각각 찾아보기
- n을 2로 나눠주기
- 재귀함수 돌리기
- 박스 중 0, 1, 2, 3번째를 찾는 부분
- x == r이고, y == c이면 cnt
- x == r+1이고, y == c이면 cnt + 1
- x == r이고, y == c+1이면 cnt + 2
- x == r+1이고, y == c+1이면 cnt + 3
코드
python
""" Z """
import sys
input = sys.stdin.readline
def dc(x, y, n):
global cnt
# 박스 안에 있는지 판단
if r < x or x + n <= r or c < y or y + n <= c:
cnt += n**2
return
# 큰 박스 -> 작은 박스로 찾아보기
if n > 2:
n //= 2
dc(x, y, n)
dc(x, y + n, n)
dc(x + n, y, n)
dc(x + n, y + n, n)
# 박스 중 0, 1, 2, 3번째를 찾는 부분
else:
if x == r and y == c:
print(cnt)
elif x == r and y + 1 == c:
print(cnt + 1)
elif x + 1 == r and y == c:
print(cnt + 2)
else:
print(cnt + 3)
sys.exit()
cnt = 0
n, r, c = map(int,input().split())
dc(0, 0, 2**n)