[programmers] 멀쩡한 사각형

12 Apr 2023 in Algorithm on Algorithm

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

유클리드 호제법(최대공약수)로 푼다.
실제 도형을 그려보고 겹치는 부분을 계산해 공식을 유추한다.
주요 공식 : 선이 지나는 가로 칸 + 선이 지나는 세로 칸 - 중첩으로 지나는 칸(세로칸 or 가로칸)

✅ 왜 GCD를 쓰는가?
대각선이 자르는 격자 수는 단순히 W + H - 1이 아니라
“대각선이 몇 번 반복되는가” 에 따라 패턴이 반복

사각형이 W와 H의 공약수만큼 나눠지면,
그 작은 패턴이 GCD(W, H)번 반복됨

예를 들어:
W = 8, H = 12 → GCD = 4
대각선은 4개의 (2, 3) 패턴을 반복함
(2 + 3 - 1) × 4 = (4) × 4 = 16개의 정사각형이 잘림

class Solution {
    public long solution(int w, int h) {
        long width = (long) w;
        long height = (long) h;

        return width*height - (width+height-gcd(width,height));
    }

    private long gcd(long w, long h){
        while(h != 0){
            long temp = w % h;
            w = h;
            h = temp;
        }
        return w;
    }
}