[백준] 14476번 최대공약수 하나 빼기

문제

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

 

풀이

 

문제풀이를 완전탐색 알고리즘으로 생각을 해보면 1~N까지의 수를 하나씩 다 빼보고 그 중에 가장 큰 최대공약수를 가질 수 있는 수를 빼는 것입니다.

하지만 완전탐색의 경우 1~N까지 숫자를 빼는 것과 숫자를 뺀 나머지 수들의 최대공약수를 구하는 과정에 있어서 시간초과가 발생할 것이라고 생각 했습니다.

 

제 풀이는 1부터 N까지 모두 빼보는 것까지는 완전탐색과 똑같은 방법입니다.

다른 점은 Segement Tree 를 이용해서 1~N까지의 최대공약수를 미리 저장해놓는 것입니다.

현재 숫자를 빼고 Segement Tree를 Update 해주고 비교해주는 거라고 보시면 됩니다.

 

소스코드

 

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 1e6;

int nums[MAX_N+1];
long long int segmentTree[MAX_N * 4];
bool flag;

long long int getIdx(long long int n){

    long long int ret = 1;

    while( ret < n){
        ret*=2;
    }

    return ret;
}

long long int gcd(long long int a, long long int b){
    return b == 0 ?  a : gcd(b,a%b);
}

void initialize(long long int firstIdx,int n){

    for(int i = firstIdx; i < firstIdx + n; i++){
        segmentTree[i] = nums[i-firstIdx];
    }

    for(int i = firstIdx-1;i >= 1; i--){
        segmentTree[i] = gcd(segmentTree[i*2], segmentTree[i*2+1]);
    }
}

void updateSegmentTree(long long int firstIdx, long long int updateIdx, long long int delta){

    long long tmpIdx = firstIdx+updateIdx;
    segmentTree[tmpIdx] = delta;
    while(tmpIdx >= 1){

        tmpIdx/=2;
        segmentTree[tmpIdx] = gcd(segmentTree[tmpIdx*2], segmentTree[tmpIdx*2+1]);
    }
}

pair<long long int, long long int> getAnswer(long long int firstIdx, int n){

    pair<long long int, long long int> ret = {segmentTree[1], nums[0]};
    
    int cnt = 0;
    for(int i = 0;i < n; i++){
        
        long long int curNum = nums[i];

        // 현재 숫자 제외
        updateSegmentTree(firstIdx, i, 0);

        // 나머지들의 최대공약수가 뺀 수의 약수인 지 판별
        if(nums[i]%segmentTree[1] != 0 && ret.first < segmentTree[1]){

            ret = {segmentTree[1], nums[i]};
        }

        if(nums[i] % segmentTree[1] == 0)
            cnt++;

        updateSegmentTree(firstIdx,i,curNum);
    }

    // 불가능한 경우
    if(cnt == n)
        flag = true;
        
    return ret;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;

    cin >> n;

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

    long long int firstIdx = getIdx(n);

    initialize(firstIdx, n);

    pair<long long int, long long int> answer = getAnswer(firstIdx,n);

    if(flag){
        cout << -1 << "\n";
    }
    else{
        cout << answer.first << " " << answer.second << "\n";
    }

    return 0;
}