[Programmers]-멀쩡한 사각형

이번 프로그래머스 문제는 멀쩡한 사각형 입니다.

아무리 생각해도 잘린 정사각형 갯수를 구하는 방법을 모르겠다..

그래서 그냥 구글링 했다. (공식 부분만…)

문제 풀이

유클리드 호제법을 이용한 최대공약수 구하기 공식에 넣는다.

조금 문제가 되었던건 long형태 범위가 벗어났다.

바꿔주니 쉬웠다.

문제풀이

• 유클리드 호제법을 이용한 최대공약수 구하기
• 공식에 넣는다.

class Solution {
    public long solution(long w, long h) {
        
        long gcd = gcd(w, h);
        
        return (long)(w*h)-(((w/gcd)+(h/gcd)-1)*gcd);//이게 그냥 공식
    }
    
    public long gcd(long a, long b){//유클리드 호제법으로 구하는 최대공약수(알아두면 좋으니 외우자)
        
        if(a%b == 0) return b;
        
        return gcd(b, a%b);
    }
}

---

유클리드 호제법 쉬우니까 알아두자.