백준 1074번: z (분할 정복, 재귀)

백준 1074번:z

해당 문제는 크게 2가지 방법으로 풀 수 있다.

1. 분할 정복 
2. 재귀

먼저 분할 정복 풀이부터 살펴보자.

분할 정복(Divide and Conquer)은 문제를 작은 문제로 재귀적으로 쪼개어, 각각을 독립적으로 해결해 마지막으로 병합하여 하나의 큰 문제를 효과적으로 해결하는 알고리즘이다. 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 검색(Binary Search) 등이 이에 속한다.

해당 문제에 이 분할 정복을 어떻게 활용할 수 있을까?
.
.
.

"주어진 행과 열 정보를 통해, 해당 행과 열이 어느 사분면에 속하는지 계산하기"

위 아이디어가 핵심이 된다. 기본적으로 Z 모양은 2x2의 사분면에 따라 움직이기 때문에, 2x2 매트릭까지 재귀하다보면 해당 위치가 어느 사분면에 속하는지에 따라 값이 결정된다.

소스코드

def Z(N, r, c):
    ans = 0

    while N:
        N -= 1

        if r < 2**N and c < 2**N:
            ans = ans

        elif r < 2**N and c >= 2**N:
            ans += 2**(2*N)
            c -= 2**N

        elif r >= 2**N and c < 2**N:
            ans += 2*(2**(2*N))
            r -= 2**N

        elif r >= 2**N and c >= 2**N:
            ans += 3*(2**(2*N))
            r -= 2**N
            c -= 2**N

    return ans

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

어느 사분면에 속하는지는 r,c값이 매트릭의 중간지점을 넘느냐,로 판단한다. 사분면에 따라 해당 위치에 어느 정도의 값을 누적시키는지 결정된다.

다음은 재귀로 풀어보자.

재귀는 Base case에 도달할 때까지 끊임없이 자기 자신을 호출하는 알고리즘으로, Base case라는 가장 작은 문제에 도달하면 호출이 종료된다.

이를 어떻게 적용할 수 있을까?
.
.
.

행과 열의 값이 2배가 될 때, 숫자가 4배가 된다.

이 규칙을 발견해야 한다. 그런데 처음에 나는 행과 열의 시작이 1이 아닌 0이라는 점을 파악하지 못해서 이 규칙을 발견하기 매우 힘들었다.

소스코드

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

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

재귀를 활용하면 문제풀이가 아주 짧아진다. 이게 재귀의 매력인 것 같다.