[백준 21870번] 시철이가 사랑한 GCD (C++)

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

21870번: 시철이가 사랑한 GCD

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
int arr[200001];

int gcd(int x, int y) //최대 공약수 구하기
{
    return (y==0 ? x : gcd(y, x%y));
}

int func(int s, int e) 
{
    int val = 0; 
    for(int i=s; i<=e; i++) //선택된 구간의 최대공약수
    {
        val = gcd(val, arr[i]);
    }
    return val;
}

int divide(int s, int e)
{
    if(s==e) return arr[s]; //원소가 한개일때

    int mid = (s + e - 1) / 2;
    
    int val1 = func(s, mid) + divide(mid+1, e); //선택되지 않은 원소의 배열은 다시, 선택된건 더하기
    int val2 = divide(s, mid) + func(mid+1, e);
    return max(val1, val2);
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    cout << divide(0, N-1);

    return 0;
}

중앙을 기준으로 왼쪽과 오른쪽을 탐색한다.

왼쪽을 골랐으면 선택한 왼쪽을 기준으로 탐색하여 해당 구역의 GCD를 구하고 이를 반환하는 동시에

선택되지 않은 구간인 중앙 기준 오른쪽을 다시 중앙을 기준으로 나눠서 왼쪽과 오른쪽을 탐색하도록 한다.

 

반대로 오른쪽을 골랐으면 선택한 오른쪽을 기준으로 탐색하여 해당 구역의 GCD를 구하고 이를 반환하는 동시에

선택되지 않은 구간인 중앙 기준 왼쪽을 다시 중앙을 기준으로 나눠서 왼쪽과 오른쪽을 탐색하도록 한다.

 

각 방법으로 GCD를 계속해서 더해주다가 제일 큰 GCD를 반환하면 된다.