[BOJ/C++] 14476: 최대공약수 하나 빼기

🏅 Gold 2

✏️ 1차 솔루션

⭐️ 유클리드 호제법으로 최대공약수 구하기
1. 벡터에 정수를 넣어두고 벡터 돌면서 하나씩 빼보기
2. 숫자를 하나 뺐다면 뺀 숫자를 제외한 모든 수의 최대공약수 구하기
➡️ 유클리드 호제법으로는 두 수에 대한 최대공약수만 구할 수 있기 때문에 두 수에 대한 최대공약수와 다른 정수를 반복해서 최대공약수를 구해서 최종적인 최대공약수 구하기
3. 뺐던 정수를 최종 최대공약수로 나눴을 때, 나누어 떨어진다면 최대공약수가 정수의 약수가 아니라고 판단
➡️ 1~3 과정 반복해서 최대 최대공약수 구하기

🚨 1차 trouble

시간초과ㅠㅠ for 문과 while 문을 중첩하고 완전탐색으로 풀이해서 그런 것 같지만 어디서 시간 낭비가 심한지는 잘 모르겠음

✏️ 최종 솔루션

⭐️ 유클리드 호제법과 DP를 응용한 누적 최대공약수로 풀이

1. 모든 정수를 배열에 저장
2. 1 번 인덱스부터 시작해서 n-1 번 인덱스까지 1번 정수부터 각 인덱스 정수까지의 누적 최대공약수를 각 인덱스에 저장 ➡️ lgcd 배열
3. 2번과는 반대로 n-1 번 인덱스부터 시작해서 1번 정수까지의 누적 최대공약수를 각 인덱스에 저장 ➡️ rgcd 배열
   ❗️ lgcd 에서 1번 인덱스 최대공약수는 1번 정수 자기자신, rgcd 도 같은 원리로 n-1 번 인덱스 최대공약수는 n-1 번 정수 자기 자신

📌 self feedback

vector 에 저장했던 게 틀린 원인이었던 것 같음
어차피 최대공약수를 누적해서 구해야하기 때문에 현재 위치 정수로부터 왼쪽에 있는 모든 숫자의 최대공약수와 오른쪽에 있는 모든 숫자의 최대공약수 두 수로 최대공약수를 산출한 것이 최종적으로 현재 위치 정수를 제외했을 때의 최대공약수가 됨 ➡️ 최대공약수 산출 범위를 이분화해서 구한 것이 관건

✏️ 최종 code

#include <iostream>

using namespace std;

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,lgcd[1000010],rgcd[1000010],v[1000010];
    cin >> n;
    
    for(int i=1;i<=n;i++) {
        cin >> v[i];
    }

    for (int i=1; i<=n; i++) lgcd[i]=gcd(v[i],lgcd[i-1]);
    for(int i=n;i>=1;i--) rgcd[i]=gcd(v[i],rgcd[i+1]);
    
    int dNum=-1;
    int bigGcd=0;
    for (int i=1; i<=n; i++) {
        int gcdRes=gcd(lgcd[i-1], rgcd[i+1]);
        if (bigGcd<gcdRes && (v[i]%gcdRes!=0)) {
            bigGcd=gcdRes;
            dNum=v[i];
        }
    }
    
    if (dNum==-1) cout << -1;
    else cout << bigGcd << " " << dNum;
}