[BOJ] 백준 21870 - 시철이가 사랑한 GCD (Javascript, 2021 연세대학교 신입생 프로그래밍 경진대회)

문제 링크

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

21870번: 시철이가 사랑한 GCD

 

풀이

각 단계마다 반으로 나눠진 배열의 왼쪽, 오른쪽 결과를 재귀적으로 모두 확인하면 됩니다.

재귀 호출의 깊이가 $O(logN)$이고, 각 레벨마다 gcd를 구하기 위해 모든 원소를 봐야 하므로 시간 복잡도는 $O(NlogN)$입니다.

 

 

정답 코드

const fs = require('fs');
const stdin = fs.readFileSync('/dev/stdin').toString().split('\n');
const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const gcd = nums => {
    const _gcd = (a, b) => (b === 0 ? a : _gcd(b, a % b));
    return nums.reduce((ret, v) => _gcd(ret, v), nums[0]);
};

const splitArray = arr => {
    const len = arr.length;
    const l = [...arr];
    const r = l.splice(parseInt(len/2, 10));
    return [l, r];
};

const main = function () {
    const n = +input();
    const p = input().split(' ').map(Number);

    const go = p => {
        if(p.length === 1) return p[0];

        const [l, r] = splitArray(p);
        return Math.max(gcd(l) + go(r), go(l) + gcd(r));
    }
    console.log(go(p));
};

main();