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

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

코딩테스트 연습 - 멀쩡한 사각형 | 프로그래머스

해당 문제를 풀고자 한다면 규칙을 찾아야한다...(알고리즘이 그렇지...)

그림을 그리다보면 선이 지나가는 사각형 집합의 모양이 일정하다는 것을 알 수가 있다.

그 사각형의 각 변의 길이는 w/최대 공약수, h/최대 공약수와 같다.

 

즉 최대공약수를 활용한 문제인데 BigInteger 클래스에는 최대공약수를 구해주는 gcd 메소드를 제공한다.

1. 사각형의 집합(블록)의 길이를 각각 구해준다.(blockW, blockH)

2. 전체 사각형의 갯수를 구한다.(sum)

3. 전체 사각형 갯수에서 선이 지나간 갯수를 뺀다.

자 그럼 여기서 선이 지나간 갯수를 구해야 답이 나오는데

직사각형에서 선이 지나간 갯수는 blockW+blockH-1에다가 최대공약수(gcd1)를 곱해주면 된다.

 

중요한 것은 해당 문제는 '직사각형'에 대한 문제이지 '정사각형'문제는 아니다.

또한 문제에서 w와 h는 각각 1억 이하의 자연수라고 했으니 int를 사용할 경우 오버플로우가 발생한다.

그러므로 long을 써줘야 한다.

public long solution(int w, int h) {
    	       BigInteger bw = new BigInteger(Integer.toString(w));
    	       BigInteger bh = new BigInteger(Integer.toString(h));
    	       
    	       BigInteger gcdInteger = bw.gcd(bh);
    	       long gcd1 = gcdInteger.longValue();
    	       long blockW = w/gcd1;
    	       long blockH = h/gcd1;
    	       
    	       long sum = w * h;
    	       
    	       return sum - gcd1*((blockW)+(blockH)-1);
    	    }