[프로그래머스/LV2] Summer/Winter Coding(2019) - 멀쩡한 사각형 - gcd (Java)

Summer/Winter Coding(2019) - 멀쩡한 사각형

🙋‍♂️ 들어가며

8 * 12

3 * 4

4 * 5

5 * 5

8 * 4

12 * 7

test_case

3,4 -> 6 - 4
2,3 -> 24 - 8
4,6 -> 24 - 8
4,5 -> 20 - 8
8,4 -> 32 - 8
10,4 -> 40 - 12
6,9 -> 54 - 12
8,12 -> 96 - 16
5,5 -> 25 - 5
12, 7 -> 84 - 18

규칙을 통해 이런 형식을 구할 수 있었다

 ( (long) (w*h) ) - (w + h) - gcd(w,h)

이는 유클리드 호제법을 통해 최대공약수를 구하는 방법으로 예시는 다음과 같다

✅ 정답 코드

class Solution {
    public long solution(int w, int h) {
        long answer = 1;
        long my_gcd = gcd(w, h);
        long to_minus = ( (long) w+h ) - my_gcd;
        answer = ( (long) w*h ) - to_minus;
        
        return answer;
    }
    
    
    static long gcd(int w, int h) {
        long a = Math.max(w, h);
        long b = Math.min(w, h);
        long res = 0;
        
        while (b != 0) {
            long remainder = (long) (a % b);
            a = b;
            b = remainder;
        }
        res = a;
        return res;
    }
    
    
}