[BOJ / Divide and Conquer] 1074. Z

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

1074번: Z

 

1074. Z

혼자 끙끙거리면서 고민하다가 풀었는데, 최종 코드가 다른 사람들이랑 많이 달라서 놀랐다.

if문으로 사분면 분할하는 과정 없이, 간단한 재귀식으로 해결한 나름 우아한 (?) 풀이인 것 같아서 뿌듯해서 올려본다.

 

 

풀이 미리보기

def Z(N, r, c):
    if N == 1:
        return r * 2 + c
    return 4 * Z(N-1, r//2, c//2) + Z(1, r%2, c%2)

N, r, c = map(int, input().split())
print(Z(N, r, c))

 

💡 아이디어

Z모양 방문으로 구성될 모든 크기의 행렬은

base = [[0, 1],
        [2, 3]]

형태로 표현할 수 있고, 각 요소는 또 같은 형태의 행렬로 무한히 쪼개질 수 있음을 고려해
재귀 함수로 구현했습니다.

행렬을 쪼개 가장 작은 유닛이 되었을 때, 이 유닛의 0행 0열의 값은 4의 배수가 되므로
N = 2일때는 출력값이 다음과 같습니다.

4**(N-1) * base[r//2][c//2] + base[r%2][c%2]
---------------------------   --------------
  기준값 (각 유닛의 0행 0열의 값)         상세값

이해를 돕기 위한 간단한 동영상 🎥

선 삐뚤삐뚤... 😅

 

🔑 풀이

base = [[0, 1],
        [2, 3]]

def Z(N, r, c):
    # base case
    if N == 1:
        return base[r][c]
    # recursive case
    return 4 * Z(N-1, r//2, c//2) + Z(1, r%2, c%2)

N, r, c = map(int, input().split())
print(Z(N, r, c))

 

조금 더 짧게 개선해보기 (주석도 지우기 🙄)

def Z(N, r, c):
    if N == 1:
        return r * 2 + c
    return 4 * Z(N-1, r//2, c//2) + Z(1, r%2, c%2)

N, r, c = map(int, input().split())
print(Z(N, r, c))