프로그래머스 lv2 멀쩡한 사각형

문제 링크

멀쩡한 사각형

풀이

class Solution {
    public long solution(int w, int h) {
        return (long) w * h - (w + h - getGcd(w, h));
    }
    
    // 재귀로 최대공약수 찾기
    public int getGcd(int a, int b){
        if(b == 0) {
            return a;
        } else {
            return getGcd(b, a % b);
        }
    }
}

소감

• 한 시간정도 규칙성을 찾았는데, 결국 못찾아서 힌트를 찾았다.
• 정답은 최대공약수를..위의 계산식처럼 가로 x 세로에서 가로 + 세로 - 최대공약수 를 빼야하는 규칙성이 있었다.
• 음...규칙성 못 찾는 것은 그럴 수 있긴한데 최대공약수라니...생각하지도 못한게 튀어나와서 좀 당황했다.
• 규칙만 알면 간단한 코드로 풀 수 있었다.
• 최대공약수를 구하는 방법은 BigInteger에 있는 gcd 함수를 사용하는 방법과 위에서 내가 한 것처럼 재귀를 이용해서 메서드를 구현하는 방법이 두 가지 있다. 기억해두자.