[프로그래머스/java] 멀쩡한 사각형 (Summer/Winter Coding 2019) + 최대공약수 구하기

https://programmers.co.kr/learn/courses/30/lessons/62048

코딩테스트 연습 - 멀쩡한 사각형

 

• 대각선 꼭짓점을 이었을 때 지나가는 사각형을 제외한 사각형의 총 개수 구하는 문제
• 최대공약수 이용하기

class Solution {
    public long solution(int w, int h) {
        long answer = 1;
        
        // W, H의 범위가 1억까지이기 때문에 long형으로 변환
        long lw = w;
        long lh = h;
        
        if(lw >= lh) { // 가로가 더 큰 경우
            answer = lw * lh - (lw + lh - gcd(lw, lh)); // 구하는 식 (최대공약수 이용)
        } else { // 세로가 더 큰 경우
            answer = lw * lh - (lw + lh - gcd(lh, lw));
        }
        
        return answer;
    }
    
    // 최대공약수 구하기
    long gcd(long big, long small) {
        while(small > 0) {
            long temp = big % small;
            
            big = small;
            small = temp;
        }
        
        return big;
    }
}