프로그래머스 멀쩡한 사각형 - js

해당 포스팅은 프로그래머스 멀쩡한 사각형 풀이를 다룬다. 문제 링크
코드는 Javascript로 작성하였으며 DP로 풀이하였다.

풀이

해당 문제는 잘라진 사각형의 규칙을 찾는 문제이다.

위의 사진을 보면 잘라진 사각형의 수가 w + h - (w와 h의 최대공약수)임을 확인할 수 있다. 따라서 유클리드 호제호법을 이용해 최대공약수를 구해 연산을 하면 된다.

전체 코드

// 잘라진 사각형의 개수 = (W + H) - W와 H의 최대공약수
function solution(w, h) {
    const GCD = (n1, n2) => {
        while (true){
            const r = n1 % n2;
            if(r === 0) return n2;

            n1 = n2;
            n2 = r;
        }
    }
    
    const r = GCD(w,h);
    return (w * h) - (w + h - r);
}

(ref) 유클리드 호제법 설명