백준 1074번: Z (G5) - Python 풀이

문제 설명

https://www.acmicpc.net/problem/1074

한수는 크기가 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

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

예제 입력 3

1 0 0

예제 출력 3

0

예제 입력 4

4 7 7

예제 출력 4

63

예제 입력 5

10 511 511

예제 출력 5

262143

예제 입력 6

10 512 512

예제 출력 6

786432

풀이 과정

전혀 감이 안 와서 헤매다가 https://www.acmicpc.net/board/view/153237 이 글을 보고 아이디어를 얻어 2^N × 2^N의 네모를 사분면으로 나누었을 때, 각 사분면의 가장 왼쪽 위의 숫자를 기준으로 규칙을 찾기 시작했습니다. ‘각 사분면의 가장 왼쪽 위의 숫자’ 를 ‘사분면의 수’ 라고 줄여서 표현하겠습니다.

이 문제는 (r, c) 위치에 적힌 값을 구해야하는 문제이기 때문에 우선 배열에 적히는 값에 대한 규칙을 찾아 봤습니다.

N=1일 때 사분면의 수는 Z 방향으로 0 1 2 3 → 1씩 증가 N=2일 때, 0 4 8 12 → 4씩 증가 N=3일 때, 0 16 32 48 → 16씩 증가 N=4일 때, 0 64 128 192 → 64씩 증가

이를 통해 N일 때 사분면의 수는 4^N-1 만큼 증가한다는 것을 알 수 있습니다.

다음엔 행과 열에 대한 규칙을 찾아 봤습니다.

N=1일 때 사분면의 수 4개가 위치하는 행과 열은 (0,0), (0,1), (1,0), (1,1) N=2일 때, (0,0), (0,2), (2,0), (2,2) N=3일 때, (0,0), (0,4), (4,0), (4,4) N=4일 때, (0,0), (0,8), (8,0), (8,8)

이를 통해 N일 때 사분면의 수 4개가 위치하는 행과 열의 값은 2^N-1 만큼 증가한다는 것을 알 수 있습니다.

이러한 규칙을 가지고 N의 크기를 1씩 감소시키면서 분할정복 방식으로 답을 구할 수 있습니다.

처음 2^N × 2^N의 네모를 사분면으로 나누었을 때 (r,c)가 어느 사분면에 해당하는지 확인하고, 그 사분면(= 2^N-1 × 2^N-1 크기의 네모)의 값을 가지고 더이상 분할되지 않을 때까지(= N이 0이 될 때까지) 이를 반복합니다.

이 과정에서 한 가지 더 고려해야 할 것은 처음 2^N × 2^N 에서 (r,c)가 어느 사분면에 해당하는지 확인한 후, 그 사분면 2^N-1 × 2^N-1 크기의 네모에서는 (r,c)가 몇 행 몇 열인지 스케일링 해주어야 합니다.

예를 들어 N=2, r=3, c=2 일 때, 0 1 4 5 2 3 6 7 8 9 12 13 10 11 14 15

이 사분면에서 (3,2)는 사분면의 수가 12인 4사분면 범위에 해당합니다.

12 13 14 15 이제 이 사분면(2^1 x 2^1)을 가지고 2^2 x 2^2 네모에서의 (3,2)에 위치한 값 즉 14는 2^1 x 2^1에서 몇 행 몇 열인가요?

네 그렇습니다. 1행 0열입니다. 이는 (3-2, 2-2)가 된 값으로, 4사분면의 경우 행과 열의 값 모두에서 2^N-1만큼 빼주어야 합니다.

1사분면은 열의 값에서 2^N-1만큼, 3사분면은 행의 값에서 2^N-1만큼 빼줍니다. 2사분면은 원래 위치 그대로 가져가도 문제가 없는 위치이기 때문에 행과 열을 이전과 그대로 가져갑니다.

이 규칙들을 가지고 재귀를 통해 분할정복을 구현하면 정답을 맞힐 수 있습니다.

정답 코드

# 18:00 ~ 19:15

N, r, c = map(int, input().split())
answer = 0

# initial_value = 사분면의 1번째 수
def recursive_z(initial_value, N, row, col):
    # 사분면의 수의 증가 단위
    value_step = 4**(N-1)
    # 행과 열의 증가 단위
    position_step = 2**(N-1)
    
    # 1사분면
    if row < position_step and col >= position_step:
        # 1사분면의 경우 사분면의 수 4개 중 2번째 값이기 때문에 현재 사분면의 수에 value_step만큼 증가된 값
        initial_value += (value_step * 1)
        # 1사분면은 열의 값에서 position_step만큼 뺀다
        col -= position_step
    # 3사분면
    elif row >= position_step and col < position_step:
        # 3사분면의 경우 사분면의 수 4개 중 3번째 값이기 때문에 현재 사분면의 수에 value_step * 2만큼 증가된 값
        initial_value += (value_step * 2)
        # 3사분면은 행의 값에서 position_step만큼 뺀다
        row -= position_step
    # 4사분면
    elif row >= position_step and col >= position_step:
        # 4사분면의 경우 사분면의 수 4개 중 4번째 값이기 때문에 현재 사분면의 수에 value_step * 3만큼 증가된 값
        initial_value += (value_step * 3)
        # 4사분면은 행과 열의 값에서 position_step만큼 뺀다
        row -= position_step
        col -= position_step
    
    # N을 1 줄임으로써 사분면 중 하나만 담는 크기로 변경
    N -= 1

    # N이 0이면 재귀 종료
    if N == 0:
        # 이때의 사분면의 수가 정답
        global answer
        answer = initial_value
        return
    # N이 0이 아니면
    else:
        # 업데이트된 사분면의 수가 (0,0)에 위치하는 네모에서
        # 업데이트된 row와 col 값이 어느 사분면에 위치하는지 찾는다
        recursive_z(initial_value, N, row, col)

# 사분면의 1번째 수는 항상 0에서 시작
recursive_z(0, N, r, c)

print(answer)

 

이상입니다.