[백준(Baekjoon)] 1074 Z

문제

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

 

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

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

 

 

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

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

 

입력

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

 

출력

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

 

제한

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

입력	출력
2 3 1	11
3 7 7	63
1 0 0	0
4 7 7	63
10 511 511	262143
10 512 512	786432

 

---

나의 풀이

[Python(파이썬)]

n, n1, n2 = map(int, input().split())
cnt = 0
def divide(n, n1, n2, cnt):
    if n > 1:   # n이 1보다 크면 4분할
    	# time : 앞에 방문한 사분면 개수(찾는 사분면 - 1), temp = 사분면 한 변 길이
        time, temp = 0, int((2 ** n) / 2)  
        if n1 >= temp:  # n1이 3, 4분면 중에 있는 경우
            time += 2
            n1 -= temp  # 찾는 행과 열이 있는 사분면의 첫번째 원소를 0, 0 으로 만들기 위해
        if n2 >= temp: # n1이 2, 4분면 중에 있는 경우
            time += 1
            n2 -= temp  # 찾는 행과 열이 있는 사분면의 첫번째 원소를 0, 0 으로 만들기 위해
        cnt += temp * temp * time   # 찾는 행과 열이 있는 사분면 앞에 있는 사분면들의 방문 횟수
        cnt = divide(n-1, n1, n2, cnt)
    else:   # 4분할 하지 못하는 마지막 사분면에서의 방문 횟수
        cnt += (n1*2 + n2 + 1)
    return cnt

print(divide(n, n1, n2, cnt)-1)

 

---

풀이 과정

 

그림 설명 1

 

1. n > 1인 경우 주어진 행과 열이 위치한 숫자가 몇 사분면인지를 구한다. 

if n1 >= temp:  # n1이 3, 4분면 중에 있는 경우
    time += 2
    n1 -= temp 
if n2 >= temp: # n1이 2, 4분면 중에 있는 경우
    time += 1
    n2 -= temp

n1 = 5, n2 = 6일 때, temp = 사분면 한 변의 길이 = 4

n1(행)이 4보다 작으면 1, 2 사분면에 위치하고 4보다 크거나 같으면 3, 4분면에 위치하고

n2(열)가 4보다 작으면 1, 3 사분면에 위치하고 4보다 크거나 같으면 2, 4분면에 위치한다. 

n1과 n2가 모두 4보다 크므로 4사분면에 위치함을 알 수 있다. 

 

 

2. 주어진 행과 열이 위치한 사분면의 전까지의 방문 횟수 구하기

cnt += temp * temp * time

3사분면까지의 횟수를 구하는 것이기 때문에 time = 3

cnt = 찾는 위치의 사분면을 오기 전에 방문한 횟수  = temp * temp * time = 4 * 4 * 3 = 48

 

 

3. 분할한 사분면에서의 주어진 행과 열의 위치 구하기

 

위에서 찾는 위치의 사분면이 4사분면이라는 것을 알아냈다. 

그럼 4사분면을 n = 2인 하나의 이차원 리스트라고 다시 생각해서 [0, 0]으로 시작한다고 생각하면 주어진 행과 열의 위치[5, 6]는 [5-temp, 6-temp] = [5-4, 6-4] = [1, 2]가 된다. 

 

 

4. 1 - 3을 반복한다. (재귀)

cnt = divide(n-1, n1, n2, cnt)

-> n - 1을 하여 4분할 하는 것 

 

 

5. 마지막 n = 1이라면 해당 위치까지의 방문 횟수를 더한다. 

    else:   # 4분할 하지 못하는 마지막 사분면에서의 방문 횟수
        cnt += (n1*2 + n2 + 1)

 

---

문제 출처

1074번: Z