[프로그래머스/코딩테스트 연습] 멀쩡한 사각형

1차 풀이... 틀렸다고 나왔다. 

 시간 초과는 다른 방법을 알아보고, 

먼저 6번이 틀린 이유를 찾아보았다. 

이유는 h/w가 더블형태라 python에서 저장될때 오차가 발생하기 때문이었다. 

따라서 다른 방법을 찾아서 시도해보기로 했다. 

 

찾은 방법은 최소공약수를 이용하는 방법이었다.

최소공배수로 두 수를 모두 나눌 경우 자연수가 나오기 때문에 이를 기준으로 계산할 경우 쉽게 계산할 수 있다.

그림으로 표현하면 쉬운데, 그 자연수를 지나는 경우 지나는 블럭은 w/a + h/a -1이 된다. 

이를 이용하면 쉽게 풀 수 있다.