백준 14476번 [최대공약수 하나 빼기](C++)-yes6686- 티스토리

백준 문제 풀이: 14476 [최대공약수 하나 빼기]

---

문제 링크: https://www.acmicpc.net/problem/14476

문제 설명:

n개의 정수 배열이 주어졌을 때, 배열에서 하나의 수를 제거했을 때 나머지 숫자들의 최대공약수를 구합니다. 그리고 제거된 숫자를 함께 출력합니다. 제거된 숫자가 최대공약수를 유지하지 못하는 경우는 제외합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1000001];
int larr[1000001];
int rarr[1000001];

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    larr[0] = arr[0];
    rarr[n - 1] = arr[n - 1];
    for (int i = 1; i < n - 1; i++) {
        larr[i] = gcd(larr[i - 1], arr[i]);
    }
    for (int i = n - 2; i >= 1; i--) {
        rarr[i] = gcd(rarr[i + 1], arr[i]);
    }
    int k = -1;
    int maxGcd = -1;

    if (arr[0] % rarr[1]) {
        maxGcd = rarr[1];
        k = arr[0];
    }
    if (arr[n - 1] % larr[n - 2]) {
        if (maxGcd < larr[n - 2]) {
            maxGcd = larr[n - 2];
            k = arr[n - 1];
        }
    }

    for (int i = 1; i < n - 1; i++) {
        int x = gcd(larr[i - 1], rarr[i + 1]);
        if (arr[i] % x) {
            if (maxGcd < x) {
                maxGcd = x;
                k = arr[i];
            }
        }
    }
    if (k == -1) {
        cout << -1;
    } else {
        cout << maxGcd << ' ' << k;
    }    
}

---

코드 설명

• 핵심 알고리즘: 좌측 및 우측에서 최대공약수를 계산하여 특정 요소를 제거한 뒤의 최대공약수를 빠르게 계산합니다.
• 구현 세부사항:
  • larr: 배열의 왼쪽부터 현재 위치까지의 최대공약수.
  • rarr: 배열의 오른쪽부터 현재 위치까지의 최대공약수.
  • 중앙의 수를 제외한 나머지 숫자의 최대공약수를 계산하기 위해 gcd(larr[i - 1], rarr[i + 1])를 사용.
  • 조건을 만족하는 최대공약수를 찾으면 해당 수와 함께 출력.
• 시간 복잡도: O(n log k) (n은 배열 크기, k는 최대공약수 계산 범위)
  • 좌측 및 우측 최대공약수 계산: O(n)
  • 개별 요소 제거 후 최대공약수 계산: O(n log k)

---

결과

주어진 배열에서 하나의 수를 제거하여 나머지 숫자들의 최대공약수를 계산하고, 해당 수와 최대공약수를 출력합니다. 조건을 만족하는 수가 없으면 -1을 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!