[JS] 멀쩡한 사각형

문제 링크

정답 풀이

const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);

function solution(w, h) {
    const divide = gcd(w, h);
    return w * h - (w + h - divide);
}

수학 문제 알고리즘이었습니다. 대각선이 지나가는 단위 정사각형의 개수를 구하는 수학적인 공식이 있습니다.

가로길이 * 세로길이 - 가로길이와 세로 길이의 최대공약수

그래서 정답은 위와 같이 구현해주면 되지만 여기서 잠깐 최대 공약수 최소 공배수를 구하는 방법에 대해서 정리하고 넘어가려고 합니다.

최대 공약수, 최소 공배수

참고 블로그

보통 유클리드 호제법을 사용해서 구합니다.

유클리드 호제법

• a,b 를 서로 나눌때, 나누어진다면 b가 최대 공약수 이다. (a > b)
• 만약 a,b가 나누어지지 않으면 b와 a를 b로 나눈 나머지를 다시 나눈다
• 서로가 나누어지면 a % b 가 최대공약수이다. 나누어지지 않는다면 위처럼 b와 a를 b를 나눈 나머지를 다시 나눈다.

function solution(num1, num2) {
    const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
    const lcm = (a, b) => a * b / gcd(a, b);
    return [gcd(num1, num2), lcm(num1, num2)];
}

최소 공배수는 두수를 곱하고 최대 공약수로 나눠준 값이므로 간단하게 a * b / gcd(a, b)로 나타냅니다.