2022.06.14 「Lv.2 멀쩡한 사각형」

문제 설명

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

 

제한사항

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

 

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

 

문제 이해

일단 그림을 뚫어지게 보았다. 항상 그랬듯이 패턴 파악에 신경을 써 보았다. 

사각형의 꼭짓점과 만나는 지점이 눈에 띄었다. 

이런 부분이 (2, 3) 주기로 반복된다. (2, 3)이 가지는 사각형의 크기는 2 x 3 = 6과 같다.

사용 가능한 사각형의 개수는 일단 2개로 보인다.

 

그럼 다음 주기인 (4, 6)을 보자. 완전한 사각형의 개수는 16개이다. 사용 불가능 사각형은 8개이다. 아직 안 보인다. 더 보자

 

다음 주기 (6, 9)이다. 사용 불가능 사각형 개수는 4개씩 늘어나는 것을 알 수 있다. 사용 불가능 사각형의 개수는 12. 사용 가능 사각형은 42개.

 

하나만 더 보자 (8, 12) 사용 불가 사각형 16개

 

음..

 

일단 x축의 증분은 2, y축 증분은 3이다. 이미지 상 주어진 가로 세로의 값은 8, 12 인데 증분은 각 2, 3 이는 곧 최대 공약수인 4로 나누어진 값임을 알 수 있다. 

일정한 패턴으로 이뤄진 사각형의 개수는 w증분(w/최대공약수) x h증분(h/최대공약수)이다. 

 

여기서 중요한 것이 기본 패턴에서 완전치 못한 사각형의 개수는 총 사각형 개수 - (w + h -1)이다. 가로지르는 직선에 걸친 중간 부분은 2개의 사각형이 걸쳐있으므로 1을 더 제해주면 된다. 반복 패턴의 횟수는 최대공약수만큼이므로

 

(w x h) - (((w / 최대공약수) + (h / 최대공약수) - 1) * 최대공약수) 가 된다. 

 

최대 공약수를 구하는 방법은 BigInteger 클래스를 사용하기로 했다.

 

풀이