(Java) 프로그래머스 - 멀쩡한 사각형

알고리즘 문제보다 수학 문제 같았다.

문제 풀이 방법에는 두 가지가 있다.

첫 번째는 규칙을 찾아 푸는 방법이고

두 번째는 기울기를 이용해서 푸는 방법이다.

나는 규칙을 찾아가면서 풀었지만 기울기를 이용한 방법이 더 간편해 보인다.

 

입력값이 int로 주어지고 w와 h값이 각각 1억 이하의 자연수이기 때문에

사용할 수 없는 사각형 계산을 하면서 인티저 오버플로가 발생할 수 있다.

따라서 입력값을 전부 long으로 형 변환 후 계산했다.

또한 최대 공약수가 1억을 넘을수는 없기 때문에 int로 선언했다.

 

최대 공약수를 구하는 방법도 세 가지가 있는데

첫 번째는 w와 h를 BigInteger로 변환하고 BigInteger에 내장된 gcd를 사용하는 방법

두 번째는 재귀를 이용한 유클리드 호제법

세 번째는 반복문을 이용한 유클리드 호제법이다.

나는 세번째 방법만 알았는데 이번 문제를 통해서 첫 번째와 두 번째 방법도 사용할 수 있다는 걸 배웠다.

세 가지 방법 모두 같은 방식으로 값이 도출되는데 그중 가장 코드가 짧은 첫 번째 방법을 사용했다.

 

최종 코드

import java.math.BigInteger;
class Solution {
    public long solution(int w, int h) {
        
        // 입력값 long으로 변환
        long lw = Long.valueOf(w);
        long lh = Long.valueOf(h);

        // 최대공약수
        int gcd = BigInteger.valueOf(lw).gcd(BigInteger.valueOf(lh)).intValue();

        // 전체 사각형
        long quadrangle = lw * lh;

        // 반복되는 사각형에서 사용할수 없는 사각형의 개수
        long reQuadrangle = ((lw / gcd) + (lh / gcd) - 1) * gcd;

        // 답
        long answer = quadrangle - reQuadrangle;
        return answer;
    }
}