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

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

21870번: 시철이가 사랑한 GCD

# 유클리드 호제법의 응용과 분할정복을 이용해서 풀었다.

 

# 흔히 유클리드 호제법을 사용한 최대공약수를 구하는 코드는 두 개의 수에 대해서만 최대공약수를

   적용할 수 있었다. 하지만, 여기서는 선택한 원소들(2개 이상) 모두의 최대공약수를 구해야 한다.

   따라서 gcd함수를 약간 변형해서 짰다.

 

# 3번조건에서 선택하지 않은 원소들 S'에 대해 다시 2번조건부터 반복하고, 계속 왼쪽에서 S/2개 선택한

   것을 쭉 따라가다 다시 돌아와서 오른쪽에서 선택한 것을 확인하는 과정이 백트래킹이라 생각해서

   BT함수를 짰다. 결과적으로 맞긴했는데, 이게 백트래킹이 맞나 싶다.

   (문제분류에는 백트래킹이 없고 분할정복, 재귀가 있긴하다.)

 

# BT함수는 이분탐색을 하는 것처럼 mid를 기준으로

   "왼쪽을 선택하면 BT(array[ :mid])와 왼쪽의 최대공약수,

   오른쪽을 선택하면 BT(array[mid: ])와 오른쪽의 최대공약수" 중 최댓값을 return해준다.

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
def gcd(lst):
	def g(x, y):
		while y:
			x, y = y, x % y
		return x
	a = lst[0]
	for b in lst[1:]:
		a = g(a, b)
	return a

def BT(array):
	mid = len(array) // 2
	if len(array) == 1:
		return array[0]
	elif len(array) == 2:
		return array[0] + array[1]
	
	return max(BT(array[ :mid]) + gcd(array[mid: ]), BT(array[mid: ]) + gcd(array[ :mid]))

mid = N // 2
if N == 1:
	print(a[0])
else:
	print(max(BT(a[ :mid]) + gcd(a[mid: ]), BT(a[mid: ]) + gcd(a[ :mid])))

(solved.ac 티어: 골드 5)

 

# 자꾸 시간초과가 뜨길래 코드가 잘못된건 줄 알고 이리저리 몇시간 고생했는데, 결국

   마지막 N이 1일때 예외처리를 안해줘서 틀린거였다..