백준 14607 - 피자 (Large)

문제 설명

피할 수 없으면 즐겨라! 파워 긍정맨

입출력 및 제한사항

풀이

n의 크기가 매우 크다! 직관적으로 생각했을 때 각 값들은 이전 값들에 의해 결정되니 DP를 사용할 수 있을 것 같다. 하지만 10억개의 데이터를 모두 저장하기에는 512MB로 공간이 모자라기 때문에 다음과 같은 두 가지 방식을 생각했다.

 

1. 메모이제이션하며 재귀 (탑-다운) -> O(logn)

2. 구해야하는 값들만 저장하여 해당 값들을 아래서부터 채우기 -> O(logn)

모든 단계는 2개의 하위로 나누어지기 때문에 시간 복잡도는 둘 다 O(logn)이다. 직접 코드로 작성해보자!

 

점화식은 다음과 같다.

dp[n] = ((n / 2) * (n - (n / 2))) + dp[n / 2] + dp[n - (n / 2)]

-> 중앙을 쪼갠 두 값을 곱한 후 쪼개진 두 값들의 이전 모든 즐거움의 함

내 코드

from functools import lru_cache

@lru_cache(maxsize=None)
def dp_dfs(n):
    if n == 1:
        return 0
    
    mid = n // 2
    ret = (mid * (n - mid)) + dp_dfs(mid) + dp_dfs(n - mid)
    
    return ret

n = int(input())
print(dp_dfs(n))

먼저 메모이제이션하며 재귀하는 방식으로 풀이했다. 파이썬에서는 lru_cache라는 데코레이터로 굉장히 간편하게 메모이제이션을 할 수 있다. 숫자를 절반으로 쪼개고 원본 수에서 쪼갠 수를 뺀 수의 값을 재귀해주었다.

여기서 메모이제이션이 정말 중요하다! 메모이제이션이 없다면 동일한 값에 대해서 중복 연산이 생기기 때문에 시간 초과가 난다. 최악의 경우 n이 10억인데 절반으로 쪼개면서 동일한 수에 대한 계산이 기하급수적으로 늘어난다. 재귀 트리의 깊이는 logn이지만 각 레벨마다 2배씩 늘어나기 때문에 결국 n에 수렴한다. 따라서 꼭! 메모이제이션을 해주어야한다.

재귀 방식으로 풀이한 코드의 실행결과

n = int(input())
if n <= 1:
    print(0)
else:
    val = {0: 0, 1: 0}  # 계산된 값 저장(메모)
    stack = [n]         # 방문 스택
    done = set()        # 자식 계산이 끝난 노드 표시

    while stack:
        x = stack[-1]
        if x in val:
            stack.pop()
            continue
        mid = x // 2
        a, b = mid, x - mid

        # 자식이 둘 다 계산됐다면 x를 계산
        if a in val and b in val:
            val[x] = a * b + val[a] + val[b]
            stack.pop()
        else:
            # 아직 계산 안 된 자식을 스택에 푸시 (중복 푸시 방지)
            if b not in val and b not in done:
                stack.append(b)
                done.add(b)
            if a not in val and a not in done:
                stack.append(a)
                done.add(a)

    print(val[n])

그리고 계산해야할 자식들의 후보들을 구해서 해당 후보들에 대해서만 값을 채워나가는 방법이다. 탑다운 재귀와 로직은 같다. 해당 풀이는 아래서부터 for문으로 값을 채워나가는데 계산해야할 자식들의 후보를 구하는 과정이 추가되어있다. 탑다운 재귀는 자동으로 구해야할 자식들만 구하지만 아래서부터 값들을 채워나가는 바텀업 DP는 어떤 값들이 필요한 값인지 확인하는 과정이 추가적으로 필요하다. 스택을 이요하여 계산된 자식을 확인하고 모든 자식이 계산되었다면 상위 노드를 계산하는 방식으로 풀이했다.

바텀업 방식으로 풀이한 코드의 실행 결과

n이 10억이어도 log를 씌우기 때문에 실제로 계산하는 것은 약 30개 정도로 매우 적다. 따라서 재귀의 오버헤드가 크게 시간을 좌우하지 않는 것 같다.

고찰

놀랍게도 이 점화식은 하나의 식으로 유도되어 O(1)의 시간으로 풀이할 수 있다. 다른 분들의 풀이를 확인하면서 유독 짧은 시간의 풀이들이 있어서 확인해보았는데, 한 줄의 식으로 코드가 완성되는 것을 보고 어떻게 이 식이 유도되는지 직접 확인해보았다.

직접 값을 넣어서 확인해보자면 n에 대해서 2차 차이가 모두 1로 일정하다. 이것은 차분법에 의해 f(n)이 2차 다항식이라는 것을 의미한다.

 

* 차분법이란 연속된 두 항의 차이로 수열의 변화율을 나타낸다.

기본 정리는 다음과 같다. "n차 다항식의 n차 차분은 상수이고, (n+1)차 차분은 0이다."

역으로, 어떤 수열의 n차 차분이 상수라면, 그 수열은 n차 다항식으로 표현된다.

 

f(n)이 2차 다항식이라면 f(n) = an^2 + bn + c의 형태로 쓸 수 있다. 이제 직접 값을 넣어가며 확인해보자

f(1) = a + b + c = 0

f(2) = 4a + 2b + c = 1

f(3) = 9a + 3b + 1 = 3

위 세 식을 연립 방정식으로 풀이하면 a = 1/2, b = -1/2, c = 0이라는 값이 나온다.

그렇다면 f(n)은 다음과 같이 작성할 수 있다.

f(n) = (1/2 * n^2) - (1/2 * n)

        = n(n-1) / 2

 

그럼 실제로 코드를 작성해서 제출해보자!

n = int(input())
print(n * (n - 1) // 2)

이렇게 식으로 유도하는 것은 실제 코딩 테스트에서는 한 눈에 알아보지 식을 유도하는 것이 더 오래걸릴 것 같아 사용하지 못하는 방식이겠지만 이런 식으로 문제 고찰을 계속 이어나가다 보면 더 좋은 방식을 찾게된다. 이것은 알고리즘 문제 뿐만이 아니라 현실의 다양한 문제에서도 적용되는 논리라는 것을 항상 기억하고 살자!