(C++) - 백준(BOJ) 14476번 : 최대공약수 하나 빼기

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

14476번: 최대공약수 하나 빼기

누적 GCD를 구하는 문제였습니다.

 

풀이방법

 a는 n개의 수를 입력받고 저장하는 배열, lgcd를 왼쪽에서 시작해 오른쪽으로 가며 누적 gcd를 구한 값을 저장하는 배열, rgcd는 오른쪽에서 시작하는 배열이라고 정의합니다.

a	8	12	24	36	48
lgcd	8	4	4	4	4
rgcd	4	12	12	12	48

 다음 예제에서 i번째 값을 지울 때 이렇게 생각할 수 있습니다.

lgcd[i-1] -> 삭제할 값 a[i] <- rgcd[i+1] 

lgcd[i-1]은 1번쨰 원소부터 i-1까지 쭉 구해온 누적 gcd이며 rgcd[i+1]은 n번째 원소부터 i+1까지 구해온 값들입니다. 따라서 gcd(lgcd[i-1], rgcd[i+1]) 만 구해준다면 i를 제외한 모든 값들의 최대공약수가 됩니다. 이 아이디어로 전체 로직을 설명하면 다음과 같습니다.

 

1. 입력 후 각 배열에 적절히 정보들을 저장합니다.

 

2. 1 ~ n까지 원소를 지웠을 때 나오는 최대의 최대공약수를 구해봅니다.

   

3. 정답을 출력합니다. 답이 갱신되지 않았다면 -1을 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int lgcd[1000010], rgcd[1000010], a[1000010], n;

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

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) lgcd[i] = gcd(a[i],lgcd[i-1]);
    for(int i = n; i >= 1; i--) rgcd[i] = gcd(a[i],rgcd[i+1]);

    int deletedNum = -1;
    int bigGCD = 0;
    for(int i = 1; i <= n; i++){
        int gcdResult = gcd(lgcd[i-1],rgcd[i+1]);
        if(gcdResult > bigGCD && (a[i] % gcdResult)){
            bigGCD = gcdResult;
            deletedNum = a[i];
        }
    }

    if(deletedNum == -1) cout << -1;
    else cout << bigGCD << ' ' << deletedNum;
}