백준 14476번 최대공약수 하나 빼기 - C++ 풀이

---

 

1. 누적 gcd인 prefix gcd와 suffix gcd 배열을 구해둔다.
2. i번째 수를 제외한 나머지 수들의 gcd는 gcd(prefixGCD[i-1], suffixGCD[i+1])이다.
3. 각 수를 제외하는 모든 경우를 탐색하며 최대공약수가 최대가 되는 경우를 찾는다.

 

1. 누적 gcd인 prefix gcd와 suffix gcd 배열을 구해둔다.

 어떤 수를 제외한 나머지 수들의 gcd를 O(1)에 구하기 위해 누적 gcd 배열을 활용할 것이다. A[0]~A[i] 까지의 최대 공약수는 prefixGCD[i], A[i]~A[N-1]까지의 최대공약수는 suffixGCD[i]라고 할 때, prefix GCD 배열과 suffix GCD 배열을 구해준다. 이 과정의 시간 복잡도는 O(N)

 

2. i번째 수를 제외한 나머지 수들의 gcd는 gcd(prefixGCD[i-1], suffixGCD[i+1])이다.

 누적 gcd 배열을 활용하여 i번째 수를 제외한 나머지 수들의 gcd를 O(1)에 구할 수 있다. i번째 수보다 앞에 있는 수들의 최대공약수인 prefixGCD[i-1]과 i번째 수보다 뒤에 있는 수들의 최대공약수인 suffixGCD[i+1]의 최대공약수를 구해주면 된다.

 

3. 각 수를 제외하는 모든 경우를 탐색하며 최대공약수가 최대가 되는 경우를 찾는다.

 각 경우를 O(1)에 구할 수 있으므로 전체 시간 복잡도는 O(N+N) = O(N).

반응형

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
    if (a < b) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a%b);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N; cin >> N;
    vector<int> v(N);
    for (int i=0; i<N; i++) cin >> v[i];
    
    vector<int> pgcd(N), sgcd(N);
    pgcd[0] = v[0];
    sgcd[N-1] = v[N-1];
    for (int i=1; i<N; i++) {
        pgcd[i] = gcd(pgcd[i-1], v[i]);
        sgcd[N-1-i] = gcd(sgcd[N-i], v[N-1-i]);
    }
    
    int maxGCD = -1, idx;
    for (int i=0; i<N; i++) {
        int GCD;
        if (i == 0) GCD = sgcd[1];
        else if (i == N-1) GCD = pgcd[N-2];
        else GCD = gcd(pgcd[i-1], sgcd[i+1]);
        
        if (GCD > maxGCD) {
            idx = i;
            maxGCD = GCD;
        }
    }
    
    if (v[idx] % maxGCD == 0) cout << -1;
    else cout << maxGCD << " " << v[idx];
    
    return 0;
}