Programmers - 멀쩡한 사각형 (Javascript)

function gcd(w, h) {   

    const mod = w % h;

    if (mod === 0) {
        return h;
    }

    return gcd(h, mod);
}


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

고민을 많이 했는데, 결과적으로 공식을 알아야 했던 문제.

우선 문제를 봤을 때 먼저 보였던 것은 같은 모양이 중복 된다는것, 그리고 중복되는 모양 마다 다음과 같이

선이 모눈종이의 점에 딱 맞게 된다는 점이다. 그리고 중복되는 구간을 구하는 방법은 가로길이와 세로길이의 최대 공약수를 구하고, 가로와 세로길이에서 최대공약수를 나누면 된다.

여기까지가 내가 생각했던 부분이고 문제의 답을 낼 수 있는 공식은 다음과 같다.

w+h-(w와 h의 최대공약수)