프로그래머스 | LV.2 멀쩡한 사각형- 구현 문풀 (Java)

⬛ 프로그래머스 | LV.2 멀쩡한 사각형- 구현 문풀 (Java)

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

프로그래머스

문제 설명

설명2

---

💚문제 접근 방식

처음에는 규칙성이 명확하게 안떠올랐다 ..

일단 큰 직사각형의 특정 비율 내에서 멀쩡한 사각형은 반복될 것이라는 생각은 들었다.

ex. 12: 8 ⇒ 3 : 2 비율

그런데 공식적으로 문제를 추리는 게 어려웠다.

gcd 최대 공약수를 먼저 구해놓고 규칙성을 잘 추려서 공식화 시키는 거였다. 

아래의 공식이 어떤 비율의 직사각형이든 계속 통한다.

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

💚 제출 코드

import java.util.*;
class Solution {
    //최대공약수
    static long gcd(long a, long b){
        if(b == 0) return a;
        return gcd(b, a % b);
    }
    
    //솔루션 함수 
    public long solution(int w, int h) {
       
        long g = gcd((long) Math.max(w, h), (long)Math.min(w, h));
        
        long answer = (long) w * (long) h - (w + h - g);
        
        return answer;
    }
}