백준 21870

문제

풀이

왼쪽에서 부터 선택할 경우 선택할 수 있는 원소의 개수는 ⌊|S|/2⌋, 오른쪽부터 선택할 경우 선택할 수 있는 원소의 개수는  ⌈|S|/2⌉로 정해져 있다.

한 방향을 선택하게 된다면 해당 방향의 원소 전체의 GCD를 선택하고 남은 원소들에서 다시 방향을 선택하는 태스크를 진행하게 된다.

그러므로 왼쪽을 선택하는 경우, 오른쪽을 선택하는 경우에 대한 모든 경우의 수를 구해 최댓값을 구하면 풀리는 문제다.

 

배열의 크기는 2*10^5이고, a<=2*10^5, b<=2*10^5라 했을때 gcd(a, b)의 시간복잡도는 log min(a, b)가 된다.

그러므로 전체 배열에 대해 gcd 연산을 하게 되는 이 알고리즘은 O(N log min(a, b))이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, arr[200001], ans;
int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a%b);
}
int getGcd(int l, int r) {
    int g = arr[l];
    for(int i=l+1; i<=r; i++) {
        g = gcd(g, arr[i]);
    }
    return g;
}
int solve(int l, int r, int n) {
    if(n == 1) return max(arr[l], arr[r]);
    int arrsize = n/2;
    int right = getGcd(l, l+arrsize-1) + solve(l+arrsize, r, n-arrsize);

    int left = getGcd(l+arrsize, r) + solve(l,l+arrsize-1, arrsize);
    return max(left, right);
}
int main() {
    cin>>N;
    for(int i=0; i<N; i++) {
        cin>>arr[i];
    }
    cout<<solve(0, N-1, N);
}