[프로그래머스] Level 2 멀쩡한 사각형 (JAVA)

문제

---

풀이

최대공약수를 이용해서 접혀진 사각형 개수를 구해야겠다는 것까지는 생각했는데, 정확한 개수 규칙을 찾아내지 못해서 검색해서 힌트를 얻었다.

1. 주어진 w와 h의 최대공약수를 calcGcd()를 통해 구한다.
2. calcGcd()는 유클리드 호제법을 사용해 최대공약수를 구한다.
3. 최대공약수 개수만큼 반복되는 블럭 유닛 내에서 접힌 사각형 개수는 (w/gcd + h/gcd) - 1이고, 이를 최대공약수만큼 곱하면 전체 접힌 사각형 개수를 구할 수 있다.

---

코드

class Solution {    
    
    public long solution(int w, int h) {
        long total = (long) w * h;
        long gcd = calcGcd(Math.min(w, h), Math.max(w, h));
        long removed = ((w / gcd + h / gcd) - 1) * gcd;
        return total - removed;
    }

    private long calcGcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            if (r == 0) return b;
            a = b;
            b = r;
        }
        return 1;
    }
}

---

참고

[프로그래머스] 멀쩡한 사각형 문제풀이 (Java)