잡다한 배똥월드

class Solution {
    public long solution(int w, int h) {
        long answer = (long) w * h;
        int temp = 0;
        
        for (int i = Math.min(w, h); i >= 1; i--) {
            if (w % i == 0 && h % i == 0) {
                temp = i;
                break;
            }
        }
        
        return answer - ((w / temp) + (h / temp) - 1) * temp;
    }
}

테스트 케이스의 위 도형을 보면 대각선이 꼭지점을 지나는 부분은

( 0 0 ), ( 2 3 ), ( 4 6 ), ( 6, 9 ), ( 8 12 ) 이다.

이걸 봤을 때 가로는 2씩, 세로는 3씩 커지는 것을 볼 수 있는데

각각 가로 세로 높이를 2와 3으로 나눠보면 4라는 숫자가 나오는 것을 알 수 있다.

가로와 세로가 8과 12라는 것을 봤을 때 최대공약수인 것을 알 수 있다.

그래서 최대 공약수를 구하고

최대 공약수를 이용해서 반복하는 칸에서 대각선이 지나가는 칸을 구해야하는데

위의 예제에서도 4칸인데, 다른 도형의 경우도 계산을 해보면 반복되는 가로 길이 + 반복되는 세로 길이 - 1이라는 공식이 나온다.

최종 공식은 전체 크기 - {(가로 / 최대공약수) + (세로 / 최대공약수) - 1 } * 최대공약수 이다.

참고 링크