[백준 14476 : JAVA] 최대공약수 하나 빼기 / 세그먼트 트리 + 유클리드

문제

---

 

 

 

풀이

---

N의 최대값이 $10^{6}$ 이기 때문에 단순한 완전 탐색(이중 루프)을 하게 되면 시간초과가 걸린다.

따라서, 세그먼트 트리를 이용한다. (세그먼트 트리가 뭔지 모른다면 ---> pangtrue.tistory.com/299)

 

만약 N=8이라면 세그먼트 트리의 모양은 다음과 같다.

[그림 1] N=8일 때 세그먼트 트리의 모양

 

배열을 이용해서 저장할 것이고, 루트 노드부터 순서대로 1번 인덱스에 값이 저장될 것이기 때문에, 가장 처음 리프 노드의 인덱스를 구한다.

// 원소의 갯수에 따른 첫 번째 리프 노드의 인덱스를 구한다.
// 예를 들어, n이 [2^2+1, 2^3]이면 첫 번째 리프노드 인덱스는 8
// n이 [2^3+1, 2^4]이면 첫 번째 리프노드 인덱스는 16
int getFirstLeafNodeIdx(int n) {
    int idx = 1;
    while (idx < n) {
        idx *= 2;
    }
    return idx;
}

 

이어서, 세그먼트 트리를 초기 셋팅하는 코드는 다음과 같다.

void init(int firstLeafNodeIdx, int n) {
    // 리프 노드 
    for (int i = firstLeafNodeIdx; i < firstLeafNodeIdx + n; i++) {
        segmentTree[i] = arr[i - firstLeafNodeIdx];
    }
    
    // 리프 노드가 아닌 노드 
    for (int i = firstLeafNodeIdx - 1; i >= 1; i--) {
        segmentTree[i] = gcd(segmentTree[i * 2], segmentTree[i * 2 + 1]);
    }
}

 

 

 

코드

---

import java.io.*;
import java.util.Arrays;

public class Main {

    private static final int  MAX_N = 1_000_000;
    private static long[] segmentTree = new long[MAX_N * 4];
    private static long[] arr;

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(br.readLine());
            arr = Arrays.stream(br.readLine().split(" "))
                    .mapToLong(Long::parseLong)
                    .toArray();

            int firstLeafNodeIdx = getFirstLeafNodeIdx(N);
            init(firstLeafNodeIdx, N);
            solve(firstLeafNodeIdx, N);
        } catch (Exception ex) {
            ex.getMessage();
        }
    }

    private static void solve(int firstIdx, int n) {
        long maxGcd = 0;    // 가장 큰 최대공약수
        long removeVal = 0; // 뺀 수
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            long curNum = arr[i];

            // 현재 숫자를 제외시킨다. (값을 0으로 갱신)
            updateSegmentTree(firstIdx, i, 0);

            // 나머지들의 최대공약수가 뺀 수의 약수인지 판별한다.
            if (arr[i] % segmentTree[1] != 0 && maxGcd < segmentTree[1]) {
                maxGcd = segmentTree[1];
                removeVal = arr[i];
            }

            if (arr[i] % segmentTree[1] == 0) {
                cnt++;
            }

            // 원래 상태로 복구.
            updateSegmentTree(firstIdx, i, curNum);
        }

        if (cnt == n) {
            System.out.println("-1");
        } else {
            System.out.println(maxGcd + " " + removeVal);
        }
    }

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

    // 배열에서 리프 노드가 저장될 첫 번째 인덱스를 반환한다.
    private static int getFirstLeafNodeIdx(long n) {
        int ret = 1;
        while (ret < n) {
            ret *= 2;
        }
        return ret;
    }

    // i~j 구간의 최대공약수를 구한다.
    private static void init(int firstLeafNodeIdx, int n) {
        // 리프 노드 (원소를 저장)
        for (int i = firstLeafNodeIdx; i < firstLeafNodeIdx + n; i++) {
            segmentTree[i] = arr[i - firstLeafNodeIdx];
        }

        // 리프 노드가 아닌 노드 (구간에 대한 연산값을 저장)
        for (int i = firstLeafNodeIdx - 1; i >= 1; i--) {
            segmentTree[i] = gcd(segmentTree[i * 2], segmentTree[i * 2 + 1]);
        }
    }

    // updateIdx: 빼고자하는 수의 인덱스
    private static void updateSegmentTree(int firstIdx, int updateIdx, long newValue) {
        int tmpIdx = firstIdx + updateIdx;
        segmentTree[tmpIdx] = newValue;
        while (tmpIdx >= 1) {
            tmpIdx /= 2;
            segmentTree[tmpIdx] = gcd(segmentTree[tmpIdx * 2], segmentTree[tmpIdx * 2 + 1]);
        }
    }
}