프로그래머스 :: 멀쩡한 사각형, javascript

😺 풀어 볼 문제

멀쩡한 사각형

간단한 풀이 설명

생각하기가 쉽지 않았던 문제이다. 어떤 규칙을 찾아서 공식을 구해야 하는 문제인데 나도 힌트를 얻기까지 혼자서 풀 지 못하였다.

최소공약수의 개념이 들어간다. 잘리는 정사각형을 자세히 살펴보면, 가로/최소공약수 세로/최소공약수의 패턴이 최소공약수만큼 반복되는것을 확인 할 수 있다. 그림으로 좀 더 이해하기 쉽게 살펴보자

예제는 12X8의 크기를 가지고 있기 때문에, 그림과 같이 3X2의 패턴들이 최소공약수인 4번만큼 반복된다.
나눠진 직사각형을 자세히 보면, 가로줄 12/4번, 세로줄 8/2번 총 5번을 통과해 다음 패턴으로 넘어간다.(겹치는 부분 포함)
따라서, 겹치는 부분을 제외한 3 + 2 - 1의 정사각형을 지나서 다음 패턴으로 넘어가게 되는데, 이 패턴이 총 4번 반복된다.
즉, 최소공약수를 구해서 계산 식에 맞게 넣어주면 해결된다.

코드

function solution(w, h) {
    var answer = 1;
    //최소공약수 :: 유클리드 호제법
    let getGCD = ( w, h ) => (h > 0 ? getGCD(h, w % h) : w);
    let GCD = getGCD(w,h)
    let unfit = (Math.floor(w/GCD) + Math.floor(h/GCD) - 1)*GCD
    answer = w*h - unfit

    return answer;
}

유클리드 호제법을 통해 최소공약수를 구해주고, 식에 맞게 넣어주면 답이 나온다.
유클리드 호제법 관련 설명은 여기를 참조하자.