백준 1074-Z (파이썬)

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

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\)

예제 입력 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

 

---

시나리오

\(2^N * 2^N\)인 2차원 배열의 모든 요소를 완전탐색해서 주어진 규칙대로 채우는 방법을 생각해볼 수 있다.

하지만 시간복잡도가 \(O(N^2)\)이고 \(1<=N<=15\)이므로 최악의 경우 \(2^{15} * 2^{15} = 1,073,741,824\)번 연산을 하게 된다. 따라서 제한시간 0.5초이내에는 절대 풀 수 없다.

 

그렇다면 어떤 방법으로 풀어야 할까? 

분할정복으로 접근해본다면 \(2^n * 2^n\)크기의 2차원 배열을 더 이상 나눌 수 없을 때까지 재귀적으로 4등분 하는 방법이 있다.

 

 

N=3, r=7, c=7일 때를 예시로 들어보자.

\(2^3*2^3\)배열을 4등분 했을 때 각 사분면의 시작점을 살펴보면

제1사분면은 0

제2사분면은 16

제3사분면은 32

제4사분면은 48부터 시작하고 있다.

따라서 제M사분면의 시작점은 다음의 공식으로 구할 수 있다.

시작점 = \(2^{N-1} * 2^{N-1} * M-1\)

 

첫번째로 4등분 하면 (7, 7)은 제4사분면에 해당된다.

n=3일 때 제 4사분면의 시작점: \(2^2 * 2^2 * 3 = 48\)

 

두번째로 4등분 하면 (7, 7)의 좌표는 (3, 3)이 되며 제 4사분면에 해당된다 시작점은 .

n=2일 때 제 4사분면의 시작점: \(2^1 * 2^1 * 3 = 12\)

 

세번째로 4등분 하면 (3, 3)의 좌표는 (1, 1)이 되며 제 4사분면에 해당된다.

n=1일 때 제 4사분면의 시작점: \(2^0 * 2^0 * 3 = 3\)

 

정리하면, N=3일 때 (7, 7) -> N=2일 때 (3,3) -> N=1일 때 (1,1)이 된다.

 

최종적으로 좌표(r,c)를 몇번째로 방문하는지 순서값을 구하기 위해선 4등분 했을 때 좌표가 몇사분면에 위치하는지 파악해서 그 시작점을 누적시키면 구할 수 있다.

 

예시의 정답: \(48 + 12 + 3 = 63 \)

 

 

정답코드

N, r, c = map(int, input().split())
ans = 0
while N != 0:
    N -= 1

    # 제1사분면
    if r < 2 ** N and c < 2 ** N:
        ans += (2 ** N) * (2 ** N) * 0
    # 제2사분면
    elif r < 2 ** N and c >= 2 ** N:
        ans += (2 ** N) * (2 ** N) * 1
        c -= (2 ** N)
    # 제3사분면
    elif r >= 2 ** N and c < 2 ** N:
        ans += (2 ** N) * (2 ** N) * 2
        r -= (2 ** N)
    # 제4사분면
    else:
        ans += (2 ** N) * (2 ** N) * 3
        r -= (2 ** N)
        c -= (2 ** N)

print(ans)

ans에 계산한 사분면의 시작점을 누적시켜준다.

그리고 제2사분면일 때는 c를,

제3사분면일 때는 r을,

제4사분면일 때는 r,c를 \(2^n\)만큼 감소시켜 4등분된 배열 내에서 몇번째 좌표에 해당하는지 계산한다.

 

 

이렇게 분할정복을 이용한 풀이법은

\(N=15\)일 때 \(N=1\) 즉, 2차원 배열의 크기가 \(2^1*2^1\)이 될 때까지 반복적으로 분할한다면 최악의 경우 단 15번만 반복하므로 빠른 시간내에 문제를 해결할 수 있다.