프로그래머스 : 멀쩡한 사각형 (최대공약수)

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

코딩테스트 연습 - 멀쩡한 사각형

이번문제는 구현하기는 쉬우나 구현을 위한 규칙을 찾기가 너무 어려운 문제인거 같다.

 

이게 정령 레벨2의 문제란 말인가...

 

최대한 규칙을 찾으려고 2차원 배열로 각각의 경우를 다 적어봤으나 찾을 수 없어, 검색을 통하여 풀이를 확인 한 뒤 구현을 하였다.

 

규칙 : 가로 * 세로 - (가로 + 세로 - 최대공약수)

 

이번문제를 통해 최대공약수는 쉽게 구할 수 있게 되었다. 그중하나인 BigInteger내장함수의 gcd 메소드도 알 수 있었다.

 

규칙을 찾느라 머리가 너무 아팠지만, 그래도 새로운 방법을 알게됬다는것에 기쁘다.

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

class Solution {
	public long solution(int w, int h) {
		long answer = 1;
		
		if(w == 0 || h ==0 ) {
			answer = 0;
			return answer;
		}
		
		if(w == 1 || h ==1 ) {
			answer = 0;
			return answer;
		}

		//최대공약수, 최소공배수 구하기 : 유클리드 호제법
//		long gcd=0;
//		long min = w < h ? w : h;
//		for(int i=1; i <= min; i ++) {
//			if(w % i ==0 && h % i ==0) {
//				gcd = i;
//			}
//		}
		
		long gcd = BigInteger.valueOf(w).gcd(BigInteger.valueOf(h)).longValue();
	
		answer = (long) w * h - (w + h - gcd);
		
		return answer;
	}
}