[백준/Python] 1074: Z

문제

https://www.acmicpc.net/problem/1074
백준 문제집 - 0x0B - 재귀

알고리즘: 재귀

---

풀이

크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다.
N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

 

2의 N제곱만큼의 행렬이 존재할때, N이 1일때부터 N이 될때까지 Z모양으로 탐색한다.
다시말해 N = 1일때가 기본값이라는 소리다.

2의 1제곱은 2니까 2x2행렬을

0 1
2 3

형식으로 방문해야하고, 이 형식을 N까지 확장해나가면 된다.

 

다만 전체 행렬값을 출력하는게 아닌 r행 c열의 값만 찾으면 되기 때문에, 행렬[r][c]가 포함되는 2x2행렬 외엔 계산하지 않아도 된다.
즉 행렬을 사분면으로 나눈 뒤 rc가 어느 사분면에 해당하는지를 찾고 그 사분면만 계산하면 되는것이다.

 

2^N x 2^N 행렬을 사등분으로 나누면 각 사등분은 2^(N-1) x 2^(N-1)이 된다.
2^(N-1)이 r, c보다 크다면 1사분면, r보다 크고 c보다 작거나 같다면 2사분면,
r보다 작거나 같고 c보다 크다면 3사분면, r, c보다 작거나 같다면 4사분면이 되겠다.
2, 3, 4분면에 해당될 경우 2^(N-1) x 2^(N-1)만큼씩의 값이 앞전에 존재한다는 소리이므로 따로 더해줘야한다.

 

예제와 같이 N, r, c가 2 3 1로 주어졌을때를 가정해보자.
함수는 make_z(n, r, c)로 크기, 행, 열 값을 인자로 지정해둔상태다.

 

4x4 행렬의 3행 1열 값을 찾아야한다.
2^(N-1)은 2가 된다. 사분면을 나누는 기준은 2행 2열이 된다.
r(3)보다 작고 c(1)보다는 크므로 3사분면에 해당된다.

그럼 3사분면을 기준으로 또 사분면을 나눈 후 위의 과정을 반복해야한다.
그리고 Z모양으로 탐색해야하므로 1, 2사분면의 크기만큼 더해줘야한다.
2 * 2^(N-1) * 2^(N-1) + make_z(N-1, r-(2^(N-1)), c)를 반환한다.

그럼 8 + make_z(1, r-2, c)가 실행되는셈이다.

이제 n, r, c는 1, 1, 1이 된다.
2^(1-1)은 0, r과 c 모두 0보다 크므로 4사분면에 해당된다.
3 * 2^(N-1) * 2^(N-1) + make_z(N-1, r-(2^(N-1)), c-(2^(N-1)))를 반환한다.

 

그럼 3 + make_z(0, 1, 1)이 실행되는데, N이 0이므로 0을 반환한다.
따라서 최종 결과값은 8 + 3 + 0 = 11이 된다.

 

전체 코드

# ⭐ 정답 코드
# 메모리: 31120KB / 시간: 36ms
from sys import stdin


N, r, c = map(int, stdin.readline().split())

def make_z(n, r, c):
    if n == 0:
        return 0

    half = 2 ** (n-1)

    if r < half and c < half:  # 1사분면
        return make_z(n-1, r, c)
    elif r < half and c >= half:  # 2사분면
        return half * half + make_z(n-1, r, c-half)
    elif r >= half and c < half:  # 3사분면
        return 2 * half * half + make_z(n-1, r-half, c)
    else:  # 4사분면
        return 3 * half * half + make_z(n-1, r-half, c-half)

print(make_z(N, r, c))

 

재귀, DP는 풀어도 풀어도 어렵다...

그래도 틀린코드라도 돌려보고 정답을 찾는게 훨씬 나은것같다. (웬만해선...^^)