[BOJ] 14476 - 최대공약수 하나 빼기 (Python, JavaScript)

 

 

아이디어

 

임의의 수 K를 중심으로 양쪽으로 누적된 두 최대공약수의 최대공약수의 최댓값을 구한다.

 

 

풀이 #1 (Python)

 

누적 합 알고리즘과 비슷한 원리로 합이 아닌 최대공약수를 누적해 리스트에 저장해 나간다.

 

import sys

input = sys.stdin.readline

def solution():

    def gcd(a, b):
        if a > b:
            a, b = b, a
        while a:
            r = b%a
            b, a = a, r
        return b

    N = int(input())
    numbers = tuple(map(int, input().split()))
    gcd_list = [0]*N
    gcd_list[1] = numbers[0]
    res = idx = -1
    for i in range(1, N-1):
        gcd_list[i+1] = gcd(gcd_list[i], numbers[i])
        if gcd_list[i+1] == gcd(numbers[i], gcd_list[i+1]):
            gcd_list[i+1] = -1
    temp = numbers[-1]
    if temp > res:
        res = gcd_list[-1]
        idx = N-1
    for i in range(N-1, 0, -1):
        temp = gcd(temp, numbers[i])
        if gcd_list[i-1] == -1:
            continue
        gcd_list[i-1] = gcd(gcd_list[i-1], temp)
        if gcd_list[i-1] == gcd(numbers[i-1], gcd_list[i-1]):
            gcd_list[i-1] = -1
        if gcd_list[i-1] > res:
            res = gcd_list[i-1]
            idx = i-1
    if res >= 0:
        print(res, numbers[idx])
    else:
        print(res)

solution()

 

 

 

풀이 #2 (JavaScript)

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function solution() {
    
    function gcd(a, b) {
        if (a > b) [a, b] = [b, a];
        while (a > 0) {
            r = b%a;
            [b, a] = [a, r];
        }
        return b;
    }
    
    const N = Number(input[0]);
    const numbers = input[1].split(' ').map(Number);
    let gcdList = Array(N).fill(0);
    gcdList[1] = numbers[0];
    let res = idx = -1;
    for (let i=1; i<N-1; i++) {
        gcdList[i+1] = gcd(gcdList[i], numbers[i]);
        if (gcdList[i+1] === gcd(numbers[i], gcdList[i+1])) gcdList[i+1] = -1;
    }
    temp = numbers[N-1];
    if (temp > res) {
        res = gcdList[N-1];
        idx = N-1;
    }
    for (let i=N-1; i>0; i--) {
        temp = gcd(temp, numbers[i]);
        if (gcdList[i-1] === -1) continue;
        gcdList[i-1] = gcd(gcdList[i-1], temp);
        if (gcdList[i-1] === gcd(numbers[i-1], gcdList[i-1])) gcdList[i-1] = -1;
        if (gcdList[i-1] > res) {
            res = gcdList[i-1];
            idx = i-1;
        }
    }
    if (res >= 0) console.log(res, numbers[idx]);
    else console.log(res);
}

solution();