멀쩡한 사각형 - Summer/Winter Coding 2019 (Java, Level 2)

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

 

처음 풀이

public long solution(int w, int h) {
    //가로로 한칸씩 움직이면서 대각선이 지나는 위치(y좌표)를 보고
    //지나가는 사각형의 개수를 계속 더해준다.

    //각 구간의 처음 지나가는 사각형의 위치
    //현재 대각선의 y좌표가 2.5라면 2 이후의 사각형부터 지나간다.
    int prevFlr = 0;
    int sumOfUnUsedSqr = 0;
    double division = h/(double)w;

    for(int i=1; i<=w; i++) {
        //한 칸 이동한 후 대각선의 y좌표를 포함한 사각형서부터
        //시작 위치 사각형까지 빼주면 한 칸 이동할 때 지나간 사각형의 개수다.
        sumOfUnUsedSqr += Math.ceil((division*i)-prevFlr;
        prevFlr = (int)Math.floor(division*i);
    }//for end

    return w*(long)h - sumOfUnUsedSqr;
}//solution() end

 

 

결과를 보니 테스트 6만 빼고 모두 통과했다.

어디서 틀렸을까 고민하다가 자바에서 실수에 대한 연산은 정확하지 않다는 조언을 보고,

division을 구하고 i를 곱하는 것이 아니라 i를 곱하고 w를 나누는 것으로 바꾸었다.

 

바꾼 풀이

    public long solution(int w, int h) {
        int prevFlr = 0;
        int sumOfUnUsedSqr = 0;

        for(int i=1; i<=w; i++) {
            sumOfUnUsedSqr += Math.ceil((long)h*i/(double)w)-prevFlr;
            prevFlr = (int)Math.floor((long)h*i/(double)w);
        }//for end

        return w*(long)h - sumOfUnUsedSqr;
    }//solution() end

 

 

다른 풀이

 

다른 글들을 참고하니 최대 공약수를 이용한 풀이가 많았다.

결과값 = (전체 크기) - (한 패턴 직사각형 당 사용하지 못하는 정사각형 크기 * 반복횟수)

result = (w * h) - (((w / 최대공약수) + (h / 최대공약수) - 1) * 최대공약수) 라는 공식을 찾아서 대입했다.

최대공약수는 유클리드 호제법에 의해 재귀함수로 구했다.

 

유클리드 호제법
A, B(자연수, A>B) 이고 A%B=R 일 때,
A, B의 최대공약수인 gcd(A,B)는 gcd(B,R)와 같다.

 

public long solution(int w, int h) {
    int gcd = gcd(w, h);
    return ((long) w * (long) h) - ((((long) w / gcd) + ((long) h / gcd) - 1) * gcd);
}//solution2() end

//최대공약수 구하는 메소드
public int gcd(int a, int b) {
    if(b==0) return a;
    return gcd(b, a%b);
}//gcd() end

 

 

for문을 돌지 않으니 특히나 오래 걸리는 테스트에서 엄청난 속도 향상이 있는 것을 알 수 있다.

 

 

---

* 자바 기본자료형 연산

- int 이하 자료형끼리 연산은 int형으로 변환 후 이뤄진다.

- 정수형 나눗셈으로 원하는 소숫점까지 얻고 싶으면 double로 casting 후 진행해야 한다.

- 자바에서 실수는 부동 소수점 방식을 사용하기 때문에 여전이 정밀도에 문제가 있다. 따라서, 소수 계산 시에는

BigDecimal 클래스를 사용한다.

 

http://kang0217.blogspot.com/2014/09/java_3.html 

https://madplay.github.io/post/the-need-for-bigdecimal-in-java