멀쩡한 사각형

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/62048

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

문제 설명 및 예시 :

코드 :

class Solution {
    public long solution(int w, int h) {
        long i = 2;
	    long min = 0;
	    long answer = 0 ;
	    //  최대공약수 
	    while(i<=(long)w&&i<=(long)h)
	    {
	    	if((long)w%i==0&&(long)h%i==0)
	    	{
	    		min=i; 
	    	}
			i++; 
	    }
	    // 직가삭형 넓이
	    long s = (long)w * (long)h;
	    // 최대공배수로 나눈 w,h
	    /*
	     * 
		           대각선이 지나는 사각형의 갯수는 격자점이 존재하는 경우와 존재하지 않는 경우로 나누어 생각
		           격자점이 존재하는 경우는 가로와 세로의 최대공약수가 2이상인 경우
		           격자점이 존재하지 않는 경우는 가로와 세로, 두 수의 최대공약수가 1인 경우
		           격자점이 존재하지 않는 경우: (가로) + (세로) - 1
		           격자점이 존재하는 경우: (가로) + (세로) - 1 - (격자점의 개수) 또는 (가로) + (세로) - (가로 세로 최대공약수)
	     */
	    if(min >=2 )
	    {
		    answer= s - ((long)w+(long)h-min);
	    }else
	    {
	    	answer= s - ((long)w+(long)h-1);
	    }
        return answer;
    }
}

직선과 만나는 점인 격자점이 있는지 규칙을 찾는것이 중요하다. 

또한, 가로세로가 1억이하 자연수이고, w 와 h 가 int 형으로 주어져 문제가 없을것 같았는데,

테스트 13부터 18 까지 오류가 났던것을 보면 테스트에서 오버플로우가 났던것 같다.

long 으로 형변환 후 테스트 결과 문제없이 돌아감을 확인했다.

결과 :