Lv 2. 멀쩡한 사각형

 

처음 코드는 부동소수점으로 인해서 오차가 발생하여 오답이 나버렸다.

두번째 코드는 부동소수점의 오류를 보완하고 더 간결하게 해결한 코드이다.

부동소수점에 대해서 알 수 있는 좋은 기회였지만... 시간이 너무 걸렸다.

//규칙이 존재한다. 
// w  8 h  12 면
// 약분해서 2, 3 이되고 2,3 에서 규칙이 총 4번 반복
// 2,3에서 지워지는 사각형 갯수 * 4 가 답이다.
// 결론은 7 12 와 같이 좀 약분했을때 큰수가 들어오면
// 빡세다는건데
// 음
// 2 3 일때
// w가 1 이동하면 1.5 이동함
// w1 이동시 2개
// 시작점이 1.5니까 나누어 떨어지지않으니까 +1해서 2
// 총 4
// 4,5 일때 한번보면 
// 1 이동하면 1.2 2
// 1.25에서 1이동하면 2
// 2.5에서 1 이동하면 2
// 3.75에서 1 이동하면 2

// 찾았다. 
//     결론적으로. 
//     들어온 수 약분 해서 작은수 만들고
//     작은수에서 규칙 해가지고 약분한만큼 나온값 * 해버리면 끝

// 규칙 method가 본질
// 0,0 에서 w가 1씩 올라가면 올라갈 수록 
// 얼마나 오르는지 확인하고 숫자 변화 있으면 +2
// 변화 없으면 +1
// 시작점이 똑떨어지면 +1
import java.util.*;

class Solution {
    // 최대 공약수 method (유클리드 호제법 사용)
    public int findGcd(int w, int h){
        if (h == 0) return w;
        return findGcd(h, w % h);
    }

    // 규칙 찾기 method
    public int regular(int w, int h){
        double sp = 0, ep = 0;
        double plus = (double)h / (double)w;
        int result = 0;
        for(int i = 0 ; i < w ; i++){
            ep += plus;
            result += (int) Math.ceil(ep) - Math.floor(sp);
            sp = ep;
        }
        return result;
    }

    public long solution(int w, int h) {
        int gcd = findGcd(w, h);
        long totalArea = (long) w * h;
        int reducedW = w / gcd;
        int reducedH = h / gcd;
        int erasedSquares = regular(reducedW, reducedH);
        return totalArea - (long) erasedSquares * gcd;
    }
}

 

기하학에 의거 ((w / ref) + (h / ref) - 1) 이게 내가 위에서 열심히 작성했던 regular 함수에서 반환되는 값보다 정확하면서 간결하게 계산하는 코드이다..

class Solution
{
	public long solution(int w, int h)
	{
		long ref = gcd(w, h);
		return ((long) w * h) - (((w / ref) + (h / ref) - 1) * ref);
	}
	public int gcd(int w, int h)
	{	
        if(h == 0) return w;
        return gcd(h,w%h);
	}
}