멀쩡한 사각형

프로그래머스

 

구현 문제.

 

---

import math

def solution(w,h):
    answer = 0
    
    # 전체 사각형 개수
    all_square_cnt = w * h
    
    # 먼저 w, h의 최대공약수로 w, h를 나눈다.
    # 나눈 값까지만 사용할 수 없는 정사각형 개수를 계산하고 그 이후는 똑같은 패턴이므로 최대공약수를 곱해주면 된다.
    gcd = math.gcd(w, h)
    w //= gcd
    h //= gcd
    # h가 더 큰 경우 h / w를 기울기, 0 ~ w까지의 값을 x좌표라고 생각하고 해당하는 y좌표를 구한다.
    if w < h:
        for i in range(w):
            check_left_val = math.floor(i * h / w)
            check_right_val = math.ceil((i + 1) * h / w)

            answer += (check_right_val - check_left_val)
    # 그 외의 경우 w / h를 기울기, 0 ~ h까지의 값을 x좌표라고 생각하고 해당하는 y좌표를 구한다.
    else:
        for i in range(h):
            check_left_val = math.floor(i * w / h)
            check_right_val = math.ceil((i + 1) * w / h)

            answer += (check_right_val - check_left_val)

    # 전체 사각형 개수에서 answer * gcd만큼 빼준다.
    return all_square_cnt - answer * gcd

 

 

로직은 금방 생각해냈는데, 문제점은

            check_left_val = math.floor(i * w / h)
            check_right_val = math.ceil((i + 1) * w / h)

 

이 코드에서 발생했다.

 

원래 처음에는 w / h 변수를 gradient라는 기울기 변수에 넣은 후,  math.floor(gradient * i) 이런 식으로 구했는데, 자꾸 1~2케이스가 틀렸다고 나왔다.

내 생각에 로직에 문제는 없었기 때문에, 구글링해본 결과 부동소수점 문제라는 걸 알게 되었다.

math.floor(h / w * i)를 하게 되면 h / w를 먼저 계산하게 되는데 그 결과가 소수인 경우 부동소수점 오차가 발생할 수 있다. 거기에 i를 곱하면 부동소수점 오차가 커질 수 있으므로 정답 계산에 오류가 발생할 수 있다.

 

그래서 위 코드처럼 i * w를 먼저 계산하고 h를 나누게 하면 부동소수점 오차를 줄일 수 있으므로 위 코드처럼 연산 순서를 바꿔야 한다.