[Python] 21870번 시철이가 사랑한 GCD

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

---

 

24/11/04

 

 

단순한 분할정복 문제다.

---

 

문제 접근 방식:

 

 

얼핏 보면 시간제한이 1초고, 나이브하게 돌리면 빡빡할 것이라고 생각이 들 것이다.

 

우리는 왼쪽과 오른쪽으로 항상 배열이 나뉨을 관찰할 수 있다.

 

왼쪽 배열의 값들의 gcd + 오른쪽 배열의 최대 혹은 오른쪽 배열의 값들의 gcd + 왼쪽 배열의 최대 중 가장 큰 값이 우리가 원하는 값임을 확인할 수 있다.

 

오른쪽 배열의 최대 혹은 왼쪽 배열의 최대 또한 분할 정복을 통해 계속 재귀적으로 구할 수 있으므로, $\mathcal{O}(N \log N)$만에 문제를 해결할 수 있다.

 

DP로 값을 저장하지 않아도 충분히 돌아감을 확인할 수 있다.(오히려 값을 저장하면 저장하는 시간때문에 더 느리다.)

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 21870번 시철이가 사랑한 GCD
# DP
'''
접근 방법:
DP[total] = max(gcd(left) + DP[right], gcd(right) + DP[left])
근데 gcd(left)나 gcd(right)을 어떻게 빠르게 구할까?
gcd(left_left, left_right) 각각의 left_left, left_right은 저장
'''
import sys
input = sys.stdin.readline
from math import gcd

gcds = dict()
DP = dict()
N = int(input())
A = list(map(int, input().split()))
def find_gcd(si, ei):
    if (si, ei) in gcds:
        return gcds[(si, ei)]
    if si == ei:
        gcds[(si, ei)] = A[si]
        return gcds[(si, ei)]
    else:
        S = ei - si + 1
        left = find_gcd(si, si+S//2-1)
        right = find_gcd(si+S//2, ei)
        gcds[(si, ei)] = gcd(left, right)
        return gcds[(si, ei)]
def dp(si, ei):
    if (si, ei) in DP:
        return DP[(si, ei)]
    if si == ei:
        DP[(si, ei)] = A[si]
        return DP[(si, ei)]
    S = ei - si + 1
    left = dp(si, si+S//2-1)
    right = dp(si+S//2, ei)
    DP[(si, ei)] = max(right + find_gcd(si, si+S//2-1), left + find_gcd(si+S//2, ei))
    return DP[(si, ei)]
ans = dp(0, N-1)
print(ans)