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

1. 문제에서 주어진 예제의 입출력에서 단위 unit의 형태를 가진 사각형을 찾은 후에

이것이 w, h의 최대공약수와 관련이 있다는 것을 발견함

 

 

2. 그 후에는 최대공약수를 구하는 메소드와

unit사각형내의 비어 있는 사각형의 개수를 unit사각형의 가로와 세로를 활용하여

규칙을 찾아내야 하는데 아무리 머리를 굴려봐도 나오지 않음

 

이 규칙을 발견하더라도

최대공약수를 구하는 메소드는 구글링을 하지 않는 이상 스스로 못짬

 

(unit의 빈 사각형 갯수)

 

 

 

class Solution {
    public long solution(long w, long h) {
        long gcd = gcd(w,h);
        long answer = w*h - (gcd * ( w/gcd + h/gcd - gcd(w/gcd, h/gcd) ));
        
        
        return answer;
    }
    
    long gcd(long a, long b) {
    
        while(b != 0) {
            long r = a % b;
            a = b;
            b = r;
        }
    return a;
    }
}