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

멀쩡한 사각형

대각선을 보니 반자동적으로, 직각삼각형 -> 빗변 -> 피라고라스 정리 가 떠올랐다.
계속 피타고라스 정리를 이용해 풀 생각만 하다 방법을 찾지 못하고 다른 이의 풀이를 보았다.
문제의 핵심은 직사각형의 대각선이 지나는 정사각형의 갯수를 구하는것이다.

풀이방법 예제

4 x 6 크기의 직사각형이 있다.

직사각형에 4cm 길이의 수평선을 그어 1 x 4 크기의 직사각형 6개로 만들어 대각선을 그어보면

대각선이 수평선을 지날때마다 새로운 사각형에 들어가니, 4 x 6 크기의 직사각형에 대각선을 그으면,
1 x 4 크기의 직사각형 6개를 건드는것을 확인할 수 있다.

마찬가지로, 6cm 길이의 수직선을 그어 6 x 1 크기의 직사각형 4개를 만들어 대각선을 그으면
대각선이 6 x 1 크기의 직사각형 4개 모두 건드는것을 확인할 수 있다.

그래서, 대각선이 수평선 혹은 수직선을 지나갈때마다 새로운 사각형을 건들게 되고,
대각선은 W 개의 수평선, H개의 수직선을 지나가 W+H개의 사각형을 건들게 된다고 볼 수 있다.
하지만 그림처럼, 대각선이 수평선과 수직선을 동시에 지나는 경우에도 새로운 사각형 1개를 건들게 되어 중복되는 수가 발생하게 된다.

이러한 중복은 W와 H의 최대공약수를 이용해 제거할 수 있다.
왜냐하면 최대공약수만큼 수평선과 수직선을 동시에 지나는기 때문이다.

소스코드

class Solution {
    public long solution(int w, int h) {
        int gcd = gcd(Math.max(w,h),Math.min(w,h));

        return ((long) w * h - (w + h - gcd));
    }
    static int gcd(int a, int b){
        if(b == 0){
            return a;
        }
        return gcd(b,a % b);
    }
}