백준 2609 JavaScript
수정하기
문서 생성 2021-11-01 22:29:54 최근 수정 2021-11-02 21:45:35
문제
풀이
최대공약수와 최소공배수를 구하는 문제이다.
하지만 학교에서 배운 공식을 사용하면 시간이 오래 걸린다. 더 빠른 방식은 "유클리드 호제법"을 이용하는 것이다.
유클리드 이름은 BAEKJOON-3053을 풀 때도 나왔다. 기원전에 이런 여러 알고리즘을 생각해내다니..정말 대단한 사람이다.
유클리드 호제법에 대한 자세한 내용은 이 블로그에서 정말 잘 설명이 되어있다.
const readFileSyncPath = require('path').basename(__filename).replace(/js$/, 'txt');// const readFileSyncPath = '/dev/stdin';let input = require('fs').readFileSync(readFileSyncPath).toString().trim().split(" ");let numbers = input.map(val => Number(val));// 최대공약수function getGCD(a, b) {while (b > 0) {let tmp = a;a = b;b = tmp % a;}return a;}let gcd = getGCD(numbers[0], numbers[1]);console.log(gcd);console.log(numbers[0] * numbers[1] / gcd);