[프로그래머스] Level2 - 멀쩡한 사각형

> 문제

문제 : [멀쩡한 사각형]

> 문제풀이

W, H 값이 1억 이하의 자연수이다.

분명 배열을 만들어서 풀이하지는 않을 것이다.

최대 공약수 또는 최소 공배수를 사용한 방법으로 접근해 보았다.

대각선으로 잘랐을 때, 대각선을 꼭지점으로 한 덩어리를 볼 수 있다.

예시에 따라 8,12 값이 주어졌을 때 네 덩어리를 볼 수 있는데, 이는 w,h값의 최대 공약수가 될 것이다.

정사각형인 4,4 값 역시 네 덩어리로 최대 공약수 4가 나올 수 있다.

이를 활용하여 덩어리는 구했고,

그 안에 대각선을 포함한 사각형은 어떻게 구할까..

대각선은 꼭지점을 제외한 세로선 h’-1개, 가로선 w’-1개를 지나는 것을 볼 수 있다.

h’, w’ 는 h,w를 최대 공약수로 나눈 값이다(네덩어리 이기에).

이때 h’, w’는 서로소이다.(최대 공약수로 나눴기에)

첫번 째 선을 지나기 전의 사각형을 포함하면, h’(3)-1 + w’(2)-1 + 1(첫번 째 사각형).

모든 덩어리를 합할 경우, 덩어리에서 최대공약수를 곱해주면 된다.

w + h - GCD(최대공약수)

다음은 유클리드 호제법으로 최대공약수를 구하였다.

class Solution {
    public long solution(int w, int h) {
        long b = Math.max(w,h);
        long s = Math.min(w,h);
        long r = 1;
        while(r > 0){
            r = b % s;
            b = s;
            s = r;
        }
        return (long)w*h - (w + h - b);
    }
}

문제 출처 : Programmers