[Lv2] 멀쩡한 사각형

programmers.co.kr/learn/courses/30/lessons/62048

코딩테스트 연습 - 멀쩡한 사각형

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다.

종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다.

이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데,

누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다.

그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다.

새로운 종이를 구할 수 없는 상태이기 때문에,

이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.

가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한사항

• W, H : 1억 이하의 자연수

입출력 예

W	H	result
8	12	80

입출력 예 설명

입출력 예 #1

가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다.

원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

---

public static long solution(int w, int h) {
    int high = Math.max(w, h);
    int low = Math.min(w, h);
    int size_high = 1;
    int size_low = 1;    // 정사각형이면 1:1 비율
    if (high > low) {
        // 정사각형이면 최대공약수는 같은 수인 그 자신, 아니면 구하기
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = low; i >= 1; --i) {
            if (low % i == 0) {
                priorityQueue.add(i);
            }
        }
        int commonDivisor = low;
        for (Integer divisor : priorityQueue) {
            if (high % divisor == 0) {
                commonDivisor = divisor;
                break;
            }
        }
        // 직사각형의 축소판의 길이를 구함.
        // 편의상 low를 가로로, high를 세로로 보고, 항상 위로 길쭉한 직사각형을 떠올리기로 함.
        size_high = high / commonDivisor;
        size_low = low / commonDivisor;
    }
    float slope = ((float) size_high) / size_low;    // y = ax + c의 1차 함수 모델에서, y절편(c)이 0인 모델을 떠올려 봄.
    long trash = 0;
    int prevY = 0;
    // size_low는 반드시 size_high보다 작으며(위로 긴 모델),
    // x가 size_low에 도달하면, y역시 size_high에 도달하며, 이는 반드시 정수임.
    // x가 0~1인 구간부터 보기로 하며,
    // 마지막 size_low는 반복문 아래에서 따로 계산한다. (1:1 정사각형 모델도 그냥 반복문 건너뛰고 계산되도록)
    for (int x = 1; x < size_low; ++x) {
        int y = (int) (slope * x);    // y의 소수점 자리를 버린다.
        // 소수점을 버리기 전의 y는 반복문 안에서 반드시 정수가 되지 못한다.
        // 최대공약수 특성상, y가 최초로 정수가 되는 곳은 x의 끝인 size_low이다.
        // (이 구간의 y는 항상 *.*가 된다.)
        // 즉, 이 구간은 y와 prevY의 차이에서 1씩 더하여도 반드시 성립한다.
        // 0.~라서 아직 한 칸을 못 넘었어도 왼쪽과 같은 진척도라 1칸을 차지하고,
        // 1.~라서 한 칸을 넘었어도, 넘은 칸과 이번 소수점 자리 1칸을 차지한다.
        trash += (y - prevY + 1);
        prevY = y;
    }
    // 처음으로 x와 y가 모두 함께 정수가 되는 종료구간.
    // prevY는 이전에서 소수점 자리를 버린채 낮아진 상태이기 때문에,
    // size_high와의 차이는 반드시 넘은 칸과 소수점 자리 모두 포함한다.
    trash += (size_high - prevY);
    // 위는 size_low와 size_high의 축소형 모델이었고,
    // 실제 직사각형은 최대공약수를 곱한만큼이므로, 곱하면 버리는 픽셀 수를 알 수 있다.
    trash *= (low / size_low);
    // 최종적으로 구하고자 하는 값은 모든 픽셀 중 버리는 픽셀 수.
    return ((long) w) * h - trash;
}