[ 프로그래머스 Lv2] 멀쩡한 사각형 (Javascript)

https://school.programmers.co.kr/learn/courses/30/lessons/62048

프로그래머스

 

 

이 문제의 핵심은 최대공약수를 사용하는 것이다. 왜 최대공약수를 사용해야 하는지 그 이유를 살펴보자. 

 

이 문제를 이해하기 위해서는 닮음비의 개념을 알아야 한다. 문제에서 사각형만 다루므로 사각형으로 예시를 들겠다. 닮음비란 두 도형이 닮음일 때, 거기서 대응하는 변의 길이의 비를 말한다. 좀 쉽게 말하면 가로, 세로 길이에 n을 곱한 것을 말한다. n을 곱함으로써 도형이 n배 커질 수 있고, 반대로 n배 작아질 수 있다. 

 

세 도형은 닮음이다 (가로 : 세로 = 3 : 2)

 

위 그림에서 세 도형은 가로 세로 비율이 3:2로 닮음이다. 첫번째 사각형의 가로, 세로 길이에 2배, 3배 한게 두번째 세번째 사각형이다. 반대로 두번째, 세번째 사각형을 첫번째 사각형으로 만드려면 두번째 사각형은 가로, 세로를 2로 나눠주면 되고, 세번째 사각형은 가로, 세로를 3으로 나눠주면 된다. 여기서 나눠주는 값은 가로, 세로 길이의 최대공약수임에 주목하자. 

 

• 첫 번째 사각형: 가로(3), 세로(2)
• 두 번째 사각형: 가로(6), 세로(4), 가로/세로 최대공약수(2)
• 세 번째 사각형: 가로(9), 세로(6), 가로/세로 최대공약수(3)

이제 위 사각형에서 유실되는 면적을 구해보자. 대각선을 그어서 선이 지나는 부분을 빨간색으로 칠하면 아래와 같다. 

 

 

그림을 보고 한 가지 규칙을 발견할 수 있다. 유실되는 사각형의 개수는 닮음 비율을 그대로 따라간다. 닮음 비율은 가로, 세로 길이의 최대공약수로 쉽게 알 수 있기 때문에 앞으로 최소 비율 사각형만 보면 된다. 

 

 

이제 대각선을 관찰해보자. 대각선이 지난 면적 중에 n*m 꼴(n,m > 1)의 사각형이 존재할 수 있을까? 절대 없다. 그림으로 살펴보자. 

 

 

우리가 관심 있는 사각형은 최소 비율 사각형임을 잊지 말자. 위 사각형들은 전부 최소 비율 사각형이다.

 

대각선이 지나는 면적 중에 n*m꼴 사각형은 존재하지 않는다. 위 그림과 같이 최소 비율 사각형에서 대각선이 지나는 면적은 무조건 계단형이다. 그리고 유실된 사각형을 윗변, 왼쪽변으로 옮겨보면 아래 그림과 같이 사각형의 가로, 세로 길이와 딱 맞는다. 참고로 이렇게 딱 맞을 수 있는 이유는 계단형 덕분이다. 왜 그런지는 혼자 생각해보자. 

 

 

이제 일반화를 해보자. 유실된 사각형의 개수는 (가로 + 세로 - 1) 개다. 1을 빼주는 왼쪽 위 모서리 부분 사각형 하나가 겹치기 때문이다.

 

이렇게 최소 비율 사각형의 유실된 사각형 개수를 알아냈다! 유실되는 사각형의 개수는 닮음 비율을 그대로 따라간다고 했었다. 그리고 닮음 비율은 최대공약수로 쉽게 구할 수 있다. 따라서 유실된 사각형의 총 개수는 아래와 같이 정리할 수 있다.

 

유실된 사각형의 총 개수 = (최소 비율 사각형의 가로 + 최소 비율 사각형의 세로 - 1) * (최대공약수)
                                        = (사각형의 가로 + 사각형의 세로 - 최대공약수)

 

 

 

정답 코드

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

const get_gcd = (a, b) => {
    while(b > 0){
        const r = a % b;
        a = b;
        b = r;
    }
    return a;
}