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

문제

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

풀이

사실 이번 문제는 도저히 모르겠어서 풀이를 참고했다.
가로가 w, 세로가 h인 격자판이 있다.
대각선을 그어서 못쓰게된 사각형을 제외하고 멀쩡한 사각형을 찾아야 하는데 그 사각형을 구하는 방법을 참고했다.
대각선을 그으면 반복되는 패턴이 생기는데 반복되는 패턴의 끝의 좌표를 예제 기준으로 적으면 아래와 같다.
[2, 3] / [4, 6] / [6, 9] / [8, 12]
그 중 처음와 끝의 점을 비교해보면
가로: 2 -> 8
세로: 3 -> 12
모두 가로길이와 세로길이의 최대공약수인 4를 곱하면 가장 끝점이 나온다는 걸 알 수 있다.
그러므로 패턴의 크기는 [가로 / 최대공약수 * 세로 / 최대공약수] 가 된다.
여기서 사용하지 못하는 사각형을 구하려면 [가로 + 세로 -1]을 해주면 된다.
-1 을 하는 이유는 가로와 세로의 길이 중에 겹치는 사각형이 하나가 존재하기 때문이다.
그리고 이 패턴은 최대공약수만큼 반복이 된다.

결과적으로,
[가로 * 세로 - 가로 + 세로 - 최대공약수]

마지막으로 자연수 1억까지 가로와 세로의 길이가 들어올 수 있기 때문에 long 형으로 바꿔주어야 한다.

코드

class Solution {
    public long solution(long w, long h) {

        long gcd = 0;
        long a = w, b = h;

		// 최대공약수 구하기
        while (b > 0) {
            long temp = a % b;
            a = b;
            b = temp;
        }

        gcd = a;

        return (w * h) - (w + h - gcd);
    }
}