[python] 백준 21870 시철이가 사랑한 GCD

김진웅·2023년 11월 4일

21870 21870번 Divide and conquer python 백준 분할정복 시철이가 사랑한 GCD 파이썬

baekjoon-study

목록 보기

26/59

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

문제

Q1. 사막에서 바늘을 찾는 방법은?

A1. 대학원생을 시킨다.

Q2. 신촌에서 자취방을 구하는 방법은?

A2. 대학원생을 시킨다.

연희동 최고의 대학원생 시철이는 오늘도 바쁘다. 그런 시철이도 이번 주말만큼은 꼭 해야 하는 일이 있었는데, 바로 자취방을 구하는 일이다!

시철이는 신촌에서 가장 아름다운 자취방을 구하고 싶다. 하지만 시철이는 매우 바빴기 때문에 직접 방을 찾아다닐 수 없었다. 그래서 시철이는 인터넷에서 본 매물번호와
$GCD$ (Greatest Common Divisor, 최대공약수)를 이용해 자취방의 아름다움을 예측하려 했다. 아름다움을 측정하는 자세한 방법은 다음과 같다.

매물번호를 나타내는 정수 배열 $S$ 가 있다. ( $|S| = N$ , $|S|$ 는 $S$ 의 원소의 개수)
배열 $S$ 의 원소를 왼쪽부터 $\lfloor \frac{|S|}{2} \rfloor$ 개 선택하거나, 오른쪽부터
$\lceil \frac{|S|}{2} \rceil$ 개 선택한다. 만약 $S$ 의 원소가 단 한 개라면 그 원소를 선택한다.
선택한 원소들의 $GCD$ 를 구한다.
선택하지 않은 원소의 배열 $S'$ 을 다시 $2$ 번부터 반복한다.
이때, 자취방의 아름다움은 $3$ 번에서 구한 $GCD$ 의 합의 최댓값으로 정의한다.

교수님의 과제로 쉴 날 없는 시철이는, 그나마 더 나은 삶을 위해 자취방을 빨리 구하려고 한다. 매물번호를 이용해 자취방의 아름다움을 계산해보자!

입력

첫째 줄에 정수 $N$ 이 주어진다. ( $1 \leq N \leq 200\,000$ )
둘째 줄에 자취방의 매물번호를 의미하는 정수 $a_1, a_2, \cdots, a_N$ 이 주어진다. ( $1 \leq a_i \leq 200\,000$ )

출력

자취방의 아름다움을 출력한다.

예제 입력 1

4
4 4 4 4

예제 출력 1

예제 입력 2

5
1 2 3 4 5

예제 출력 2

아이디어 스케치

엄청나게 크고 방대한 문제를 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하는 분할 정복(Divide and Conquer) 알고리즘을 이용하는 문제이다.
중앙을 기준으로 구역을 나눠 각 구역의 GCD를 구하고 구한 GCD를 반환하는 방식으로 풀면 된다.
왼쪽부터 시작하는 경우와 오른쪽부터 시작하는 경우로 나누어 수행한 후 더 큰 값을 출력하면 된다.

코드 분할 설명

def gcd(a, b):      # 유클리드 호제법을 이용한 최대공약수 탐색
    while b != 0:
        c = a % b
        a = b
        b = c
    return a

유클리드 호제법을 이용하여 최대공약수를 구하는 함수이다.

def max_sum(start, end):
    if start == end:    # 리스트의 크기가 1일때
        return num[start]   # 한개의 원소를 반환
    if start + 1 == end:    # 리스트의 크기가 2일때
        return num[start] + num[end]    # 두개의 원소를 더해서 반환

    mid = (end - start + 1) // 2    # 중간 인덱스 계산(구역을 반으로 나누기 위해)

이 문제의 핵심 함수인 max_sum함수의 도입부분이다.
start인덱스와 end인덱스를 전달받아 종료조건을 명시하고 있다. 리스트의 크기가 1일때 한개 원소의 값을 반환하고 리스트의 크기가 2일때는 두 개의 원소를 더해서 반환한다. 위 두가지 조건에 해당되지 않는 경우에는 구역을 반으로 나누기 위해 중간 인덱스를 계산하여 mid에 저장한다.

# 왼쪽 부터 원소를 선택 하는 경우
    left_sum = 0
    idx = start
    g = num[start]
    while idx <= (start + mid - 1): # 왼쪽 구역 탐색
        g = gcd(g, num[idx])
        idx += 1
    left_sum = g + max_sum(start + mid, end)    # start값을 start+mid로 한 후 재귀호출

구역을 반으로 나눈 후 왼쪽 구역부터 원소를 선택하는 경우를 구현한 코드이다.
start인덱스부터 mid-1인덱스, 즉 왼쪽 구역의 원소들의 최대공약수를 구하여 g에 저장한 후 start값을 start+mid로 한 후 재귀호출을 수행한다. 재귀호출을 수행하면 오른쪽 구역을 다시 반으로 나누어 새로 나누어진 중간값의 왼쪽구역의 원소의 최대공약수를 구한 후 또다시 오른쪽 구역을 반으로 나눈다. 위 행위를 종료조건에 해당될 때 까지 수행한다.

 # 오른쪽 부터 원소를 선택 하는 경우
    right_sum = 0
    idx = start + mid
    g = num[end]
    while idx <= end: # 오른쪽 구역 탐색
        g = gcd(g, num[idx])
        idx += 1
    right_sum = g + max_sum(start, start + mid - 1) # end값을 start + mid -1로 한 후 재귀호출

    return max(left_sum, right_sum)     # 왼쪽 부터 원소를 선택 하는 경우와 오른쪽 부터 원소를 선택 하는 경우중 더 큰 값 반환

이전 코드와 다른점은 구역을 반으로 나눈 후 오른쪽 구역부터 원소를 선택한다는 것이다. max_sum함수는 왼쪽부터 선택하는 경우와 오른쪽부터 선택하는 경우 두 가지의 결과값을 구한 후 더 큰 값을 반환한다.

전체코드

import sys

def gcd(a, b):      # 유클리드 호제법을 이용한 최대공약수 탐색
    while b != 0:
        c = a % b
        a = b
        b = c
    return a

def max_sum(start, end):
    if start == end:    # 리스트의 크기가 1일때
        return num[start]   # 한개의 원소를 반환
    if start + 1 == end:    # 리스트의 크기가 2일때
        return num[start] + num[end]    # 두개의 원소를 더해서 반환

    mid = (end - start + 1) // 2    # 중간 인덱스 계산(구역을 반으로 나누기 위해)

    # 왼쪽 부터 원소를 선택 하는 경우
    left_sum = 0
    idx = start
    g = num[start]
    while idx <= (start + mid - 1): # 왼쪽 구역 탐색
        g = gcd(g, num[idx])
        idx += 1
    left_sum = g + max_sum(start + mid, end)    # start값을 start+mid로 한 후 재귀호출

    # 오른쪽 부터 원소를 선택 하는 경우
    right_sum = 0
    idx = start + mid
    g = num[end]
    while idx <= end: # 오른쪽 구역 탐색
        g = gcd(g, num[idx])
        idx += 1
    right_sum = g + max_sum(start, start + mid - 1) # end값을 start + mid -1로 한 후 재귀호출

    return max(left_sum, right_sum)     # 왼쪽 부터 원소를 선택 하는 경우와 오른쪽 부터 원소를 선택 하는 경우중 더 큰 값 반환

n = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))   # 매물번호를 저장할 리스트

print(max_sum(0, n - 1))