[Javascript] 멀쩡한 사각형(62048)

문제링크

 

if(w > h){
    answer = w*h-((Math.ceil(w/h)) * h)
}else if(h > w){
    answer = w*h-((Math.ceil(h/w)) * w)
}else{
    answer = w*h-w
}

하지만 기울기에 따라서 2,3,2,3,2,3 이런식으로 선과 겹치는 부분을 인지하지 못해서 다시 접근하였다.

주어진 그림을 통해 흰 부분의 패턴을 파악하면
3 * 7 그림은 9개
4 * 7 그림은 10개
5 * 7 그림은 11개
6 * 7 그림은 12개
다들 넓이 + 높이 - 1이다.

좀 더 다른 예제를 살펴보면

3 * 6 그림은 6개
4 * 6 그림은 8개
이들은 각각 아래의 패턴을 갖는다.
높이 + 넓이 - 3
높이 + 넓이 - 2 
또한 이들은 점과 점이 연결된 구간이 존재한다. => 나누어 떨어지는 부분이 있음

결론적으로 두 수의 최대 공약수(점과 점이 만나는 블록의 개수)를 구하면 이 문제를 해결할 수 있다.

※ 흰칸의 개수 : w + h - (최대 공약수)

 

function solution(w, h) {
    let answer = 1;
    const gcd = getGCD(w, h);
    answer = w * h - (w+h-gcd);
    return answer
}

function getGCD(w, h) {
    const mod = w % h;
    
    return mod === 0 ? h : getGCD(h,mod);
}