백준 14476 최대공약수 하나 빼기 python

최대공약수 뺴기 누적합 문제 해결

 

 

1. 왼쪽부터 차례로 누적 최대공약수를 구합니다.

2. 오른쪽부터 차례로 누적 최대공약수를 구합니다.

 

[8, 12, 24, 36, 48]

 

 

예를 들어 index 0의 8이 빠지면 right_prefix_list[1]이 최대 공약수 입니다.

index 1이 빠지면 left_prefix_list[1 - 1]과 right_prefix_list[1 + 1]의 최대 공약수가 전체의 최대 공약수입니다. 이 아이디어를 바탕으로 문제를 해결할 수 있습니다.

 

 

문제 오류

 

12는 빠진 수 8의 약수가 아니기 때문에 정답이 될 수 있다.  -> 12는 8로 나누어 떨어지지 않기 때문에 정답이 될 수 있다. 

예외 케이스 24는 8의 약수가 아니지만, 이것이 반례가 됩니다. 88%에서 막힌 이유

 

정답 코드

import math
import sys
si = sys.stdin.readline 
N = int(si())
arr = list(map(int, si().split()))

answer = -1
answer2 = -1
# def gcd(x, y):
#     while y:
#         x, y = y, x % y

#     return x

left_prefix_list = [arr[0]]
right_prefix_list = [arr[-1]]


# left prefix
left = left_prefix_list[0]
for i in range(1, N):
    left = math.gcd(left, arr[i])
    left_prefix_list.append(left)

# right prefix
right = right_prefix_list[0]
for i in range(N-2, -1, -1):
    right = math.gcd(right, arr[i])    
    right_prefix_list.append(right)

right_prefix_list.reverse()

for index in range(N):
    if index == 0:
        val = right_prefix_list[index + 1]
        # 이때, 최대공약수는 K의 약수가 되면 안 된다.
        
    if 0 < index < N - 1:
        left_val = left_prefix_list[index - 1]
        right_val = right_prefix_list[index + 1]
        val = math.gcd(left_val, right_val)

    if index == N-1:
        val = left_prefix_list[index - 1]
    
    if (arr[index] % val == 0) : continue 

    if answer < val:
        answer = val
        answer2 = arr[index]

if answer == -1:
    print(-1)
else:
    print(answer, answer2)