멀쩡한 사각형 (최대공약수)

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/62048/solution_groups?language=java

프로그래머스

 

문제 풀이

대각선이 격자를 가로지르면서 

 

• 세로선을 넘을 때마다 새로운 칸으로 진입 → W번 발생
• 가로선을 넘을 때마다 새로운 칸으로 진입 → H번 발생
• 그런데 대각선이 격자점(모서리)을 정확히 통과하는 순간에는 가로선과 세로선을 "동시에" 넘기 때문에, 칸 진입이 한 번만 카운트

전체 그림에서 격자점을 정확히 통과하는 횟수는 

gcd(W, H) − 1번 (양 끝 꼭짓점 제외)이고, 시작 칸 1칸을 더하면

 

선이 지나가는 칸 수 = W + H - gcd(W, H)

 

이 된다.

 

최종식은 

 

전체 칸 수 - 대각선이 지나가는 칸 수

= W×H - (W + H - gcd(W, H))

 

이 된다.

 

 

작성한 코드

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

    // 유클리드 호제법
    public long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}