[백준] 2436 공약수 (Javascript)

문제

BOJ2436_공약수

풀이

요구사항

두 자연수 a,b가 입력으로 주어진다. a는 어떤 자연수 두 수의 최대공약수이고, b는 그 두 수의 최소공배수이다.
이때 두 자연수는 여러 쌍이 나올 수도 있다. 그때는 두 수의 합이 가장 작은 쌍을 출력하되 두 수에서 작은 수를 먼저 오도록 출력하라.

해결방안

자연수 n,m의 최대공약수가 a이고, 최소공배수가 b라고 하자.
최대 공약수를 구할 때 두 수가 공통된 수로 나누어지지 않을 때까지(서로소가 될 때까지) 인수분해를 진행한다. 두 서로소를 x,y라고 하자. 그럼 $a \times x \times y = b$ 이다.

a와 b는 입력으로 주어진다. a=6, b=180일 때 이를 위 식에 대입해보자. $6 \times x \times y = 180$ 이고, 6을 이항하여 전개하면 $x \times y = 30$이 된다.
그럼 이제 곱했을 때 30이 되는 x,y쌍을 찾으면 된다.

중첩 반복문을 통해 일일히 x,y를 1씩 증가시키며 비교하는 방법도 있지만 중첩 반복문을 사용하지 않고도 y를 이항시켜 $x = 30 \div y$꼴로 만들면 y만 1씩 증가시켜도 x를 구할 수 있다.

const right = b / a;
for (let i = 1; i <= right / 2 + 1; i++) {
    y = i;
    x = right / y;
}

반복 횟수는 $b \div a \div 2+1$번 진행하는데, $b \div a$번 진행할 경우 i가 $b \div a \div 2$ 이상 증가할 경우 중복된 연산을 수행하기 때문이다. 예를 들면 i=2일 때 y=2, x=15이고, i=15일 때, y=15, x=2 이런 식으로 순서만 바뀌고 중복된 연산을 수행한다.

따라서 2로 나눠주어 중복된 연산을 방지하고, +1을 해주어 a=2, b=2와 같을 경우에도 정상적으로 처리해주도록 한다.

그리고 x가 자연수가 아닐 경우 연산을 수행하지 않고 다음 반복문으로 이동한다.

if (x - Math.floor(x) > 0) continue;

그리고 $x \times y = 30$ 공식이 성립되는지 확인하고, x와 y가 서로소인지 확인한다.

if (x * y === right && check(x, y)) {
        n = a * x;
        m = a * y;
        if (n + m < min) {
            min = n + m;
            answer = m + ' ' + n;
        }
    }

check 함수는 x와 y가 서로소인지 판별해주는 함수다.

// x, y가 서로소인지 판별
function check(x, y) {
    let bigger = x > y ? x : y;
    for (let i = 2; i < bigger / 2; i++) {
        // x,y가 같은 수로 나누어떨어질 경우 서로소가 아님
        if (x % i === 0 && y % i === 0) return false;
    }
    return true;
}

만약 공식이 성립한다면 $a \times x$로 n을 구할 수 있고, $a \times y$로 m을 구할 수 있다. 그리고 합이 가장 작은 쌍을 구해야 하기 때문에 최솟값일 경우 최솟값을 갱신해준다.

또한 y가 x보다 작기 때문에 m이 n보다 작다. 따라서 answer 변수에는 m이 먼저 오도록 해준다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [a, b] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
let min = Infinity;
let answer = '';

let x, y, n, m;
const right = b / a;

// x, y가 서로소인지 판별
function check(x, y) {
    let bigger = x > y ? x : y;
    for (let i = 2; i < bigger / 2; i++) {
        // x,y가 같은 수로 나누어떨어질 경우 서로소가 아님
        if (x % i === 0 && y % i === 0) return false;
    }
    return true;
}
for (let i = 1; i <= right / 2 + 1; i++) {
    y = i;
    x = right / y;
    // x가 소수일 때는 무시
    if (x - Math.floor(x) > 0) continue;
    if (x * y === right && check(x, y)) {
        n = a * x;
        m = a * y;
        if (n + m < min) {
            min = n + m;
            answer = m + ' ' + n;
        }
    }
}
console.log(answer);

제곱근 이용

반복문을 돌릴 때, 제곱근을 이용하면 반복 횟수를 줄여서 속도를 개선시킬 수 있다.

위 코드에서 반복문을 $\div 2$ 번 실행시켜주는 것은 여전히 무의미한 연산을 발생시킨다.

이는 제곱근을 이용해서 속도를 개선시켜줄 수 있다.

$x \times y = n$ 이라고 할 때, 사실 반복문을 $\sqrt{n}$ 번 넘게 수행해주는 것은 무의미하다.

$x \times y = n$ 일때,
$x \le \sqrt{n} \quad and \quad y \ge \sqrt{n}$ 이거나,
$x \ge \sqrt{n} \quad and \quad y \le \sqrt{n}$ 이다.
즉 x가 커지면 그만큼 y가 작아진다는 소리다.

우리는 y의 값이 정해지면 x의 값은 $x=\frac{n}{y}$ 에 의해 자동으로 정해지도록 코드를 작성했다. 이는 y의 값이 커짐에 따라 x의 값은 작아짐을 의미한다.

따라서 y의 값만 $\sqrt{n}$ 까지 증가시키면 된다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [a, b] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
let min = Infinity;
let answer = '';

let x, y, n, m;
const right = b / a;

// x, y가 서로소인지 판별
function check(x, y) {
    let bigger = x > y ? x : y;
    for (let i = 2; i < Math.sqrt(bigger); i++) {
        // x,y가 같은 수로 나누어떨어질 경우 서로소가 아님
        if (x % i === 0 && y % i === 0) return false;
    }
    return true;
}
for (let i = 1; i <= Math.sqrt(right); i++) {
    y = i;
    x = right / y;
    // x가 소수일 때는 무시
    if (x - Math.floor(x) > 0) continue;
    if (x * y === right && check(x, y)) {
        n = a * x;
        m = a * y;
        if (n + m < min) {
            min = n + m;
            answer = m + ' ' + n;
        }
    }
}
console.log(answer);