[Programmers Lv2, Java] 멀쩡한 사각형

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요. 제한사항

• W, H : 1억 이하의 자연수

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

프로그래머스

 

---

처음에 잠깐 헛짓거리하다가 정신잡고 다시푸니까 금방 푸는 문제였다.

다만, 저번 글에도 적었듯이 맘에 안드는 자료형때문에 풀기에 난잡해지는 문제였어서... 별로 맘에는 들지 않는다.

 

처음 문제를 푸는데 접근했던 방법은 기울기였다.

근데 기울기인데 좀 이상하게 접근해서, 색칠된 사각형(잘리지 않은)들의 개수에서 규칙을 찾고있었다.

3*3+2*2.. 어쩌구...

 

그러다가 이건 뭔가 아닌거같다라는 생각이 반짝 들어서 다음으로 했던 방법은

잘리는 사각형들의 크기를 구하는것이었다.

예를 들어 예제로 나왔던 8*12 사각형의 경우 (8, 0)과 (0, 12)를 지나는 직선이 사각형을 자르는 것이므로, 이에 대한 일차식을 찾아서 풀면된다는 발상이었다.

 

일단 반복수를 줄이기위해 가로,세로중 긴쪽을 가로로 두고 기울기를 구한뒤 계산했다.

예를 들어 x=0~1 구간에서 잘리는 사각형은 Math.ceil(1 * incline) - Math.floor(0 * incline) 이다.

이걸 모든 x구간을 크기 1로 쪼갠 뒤 반복해서 빈칸의 개수를 구해서 전체 w*h에서 뺀다는 생각이었다.

 

문제는, double의 부동소수점 표시가 15자리까지인게 문제였는지 작은수의 계산에서는 아무 문제도없다가 큰수의 문제로 가면 오차가 생기기 시작했다는 것이었다.

그래서 이걸 대체 어떻게 해야하나... 하다가 BigDecimal로 대체했다.

계산횟수도 줄이기 위해 Math.floor(x * incline)을 모두 더한뒤 2를 곱해서 안잘린 사각형의 개수를 직접 구하는 방식으로 변경했다.

이래도 속도가 굉장히 느리다...

 

크기제한때문에 질문글이랑 이런거 들어가보니까 최대공약수? 공배수? 뭐 그런말들 있던데 그건 어떻게하는건지 모르겠다. 그것에 대한 아무런 생각도 떠올리지 못했어...