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

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

문제풀이

규칙을 찾아내는 문제인데... 사실 잘 모르겠다. 시험에서 마주친다면 풀지 못했을 것 같다.

1. w, h의 최대공약수를 구한다.
2. 선이 그어진 모든 칸의 갯수는 gcd((w / gcd) + (h / gcd) - 1) 이다.
3. 전체 칸에서 위에서 구한 칸의 갯수를 뺀다.

• w, h는 각각 최악의 경우에 1억이다. 따라서 long으로도 최악의 경우를 커버할 수 없다.
• BigDecimal을 사용한다.

구현코드

import java.math.*;
import java.util.*;

class Solution {
	public long solution(int w,int h) {
    		int gcd = getGcd(w, h);
                int sub = gcd * ((w / gcd) + (h / gcd) - 1);

                BigDecimal amount = new BigDecimal(w).multiply(new BigDecimal(h)); 
                amount = amount.subtract(new BigDecimal(sub));

		return amount.longValue();
	}
    
        public int getGcd(int a, int b){
            if(b == 0) return a;
            else return getGcd(b, a % b);
        }
}