[Python 3] BOJ - 14476 "최대공약수 하나 빼기"

 # 문제 링크

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

14476번: 최대공약수 하나 빼기

 

 # 풀이

  개인적으로 이 문제의 핵심은 prefix sum과 suffix sum이라고 생각한다. 물론 세그먼트 트리를 사용해도 무방하지만, 더 간단하게 풀 수 있다. 현재 k번째 수를 제외하게 되면 남는 구간이 [0, k - 1]과 [k + 1, n - 1]이다. 그런데 gcd연산은 결합법칙이 성립하므로 즉, gcd(a,b,c) = gcd(gcd(a, b), c)이므로 누적합과 같이 볼 수 있다.

<그림 1. 예제 1의 prefix(좌), suffix(우) sum>

다만, 누적합은 시작점이 0이 아닌 특정 구간에 대한 누적합도 구할 수 있으나, gcd 누적합의 경우는 시작점이 0이 아닌 특정 구간에 대한 누적합을 구할 수 없다는 것이 차이점이다. 따라서, prefix sum과 suffix sum을 구한다면, 현재 k번째 인덱스를 제외한다면, pf[k - 1]과 sf[k + 1]의 gcd가 최종 gcd가 되고 시간안에 모든 경우를 탐색할 수 있으므로 정답을 구할 수 있다.

 

 # 코드

import sys, math

# 입력부
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

# pf_gcd : 0부터 i까지의 gcd를 저장하는 리스트
# sf_gcd : i부터 n - 1까지의 gcd를 저장하는 리스트
pf_gcd = [0] * (n + 1)
sf_gcd = [0] * (n + 1)

pf_gcd[0] = arr[0]
for i in range(1, n):
    pf_gcd[i] = math.gcd(pf_gcd[i - 1], arr[i])
sf_gcd[n - 1] = arr[n - 1]
for i in range(n - 2, -1, -1):
    sf_gcd[i] = math.gcd(sf_gcd[i + 1], arr[i])
    
# ans : 정답 배열
ans = []
for i in range(n):
    # left : [0, i - 1]까지의 gcd
    left = pf_gcd[i - 1]
    # right : [i + 1, n - 1]까지의 gcd
    right = sf_gcd[i + 1]
    # res : i번째 수를 제외한 최종 gcd
    res = math.gcd(left, right)
    # 약수가 아니라면 정답 배열에 저장
    if arr[i] % res == 0:
        continue
    ans.append((res, arr[i]))
    
# 정렬 후 정답출력
ans.sort(reverse=True)
print(' '.join(map(str, ans[0])) if ans else -1)