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

문제

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다.
종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다.
이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다.
그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다.
새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

풀이

도저히 풀 수 없었다...
주어진 W와 H에 대하여 면적에 집중했었다.
면적에 따라서 사각형의 갯수가 결정되고, 또한 W와 H는 서로 바뀌어도 구하는 사격형은 같아지므로,
이전의 갯수에서 영향을 받는다고 생각해서 DP를 이용해서 풀이하려고 했다.
그러나 이는 잘못된 생각이었다.
w와 h가 작을때는 면적에 따라서 같은 사각형을 구할 수 있었지만, 크기가 커짐에 따라서 그 갯수가 달라졌다.
가령 W가 2고 H가 8일때 가능한 사각형은 8개지만,
W가 4고 H가 4일때는 가능한 사각형은 12개 이지만 서로 면적은 같다.
따라서 W와 H에 따라서 사각형이 달라진다는 결과를 알았지만, 이 방법으로는 풀이할 수 없었기에 결국 다른 방법을 참고하였다.

W가 8이고 H가 12일때, 지나는 점의 갯수는 8과 12의 최대공약수(4)이다.
이를 기억하자.

• 최대공약수가 1일때

최대 공약수가 1일때 지나는 점의 갯수는 없다.
w와h에 따라서 지나는 사각형이 결정되는데 이는 곧 w + h - 1이 된다.
(그려보면 알 수 있다.)

• 최대공약수가 1보다 클 때

최대공약수가 1보다 크면 위의 좌표상의 그래프처럼 작은 사각형이 최대공약수 갯수만큼 구성되는 것을 알 수 있다.
작은 사각형에서 지나는 사각형은 최대공약수가 1일때 구하는 방식과 같다.
따라서 g(w / g + h / g - 1) 이므로 w + h - g로 정리할 수 있다.

그렇다면 전체 사각형의 갯수에서 지나는 사각형의 갯수를 빼면 되므로
w * h - (w + g - gcd(w, h))로 정리할 수 있다.
gcd는 최대공약수...
w와 h는 1억이 넘으므로 long으로 변환해서 구해야 한다.

import java.util.*;
import java.lang.*;

class Solution {
    public long solution(int w, int h) {
        long a = (long) w;
        long b = (long) h;
        return a * b - (a + b - gcd(a, b));
    }

    static long gcd(long w, long h) {
        long min = w < h ? w : h;
        long gcd = 0;
        for(long i = 1; i <= min; i++) {
            if (w % i == 0 && h % i == 0) {
                gcd = i;
            }
        }

        return gcd;
    }
}

https://github.com/Win-9/Algorism/tree/main/programers/%EB%A9%80%EC%A9%A1%ED%95%9C%20%EC%82%AC%EA%B0%81%ED%98%95