[프로그래머스] 멀쩡한 사각형

멀쩡한 사각형

출처 : [프로그래머스] 멀쩡한 사각형 (Level 2)

문제를 풀려면 좌표평면에 그려보고 두가지 포인트를 잡아야한다.

예시로 주어진 w=8, h=12인 사각형에 그려지는 직선은
좌표평면에서 (0,0) (8,12)를 지난다.

정리해본 식 : $y = \frac{12}{8}x = \frac{6}{4}x = \frac{3}{2}x$

1. 첫번째 포인트
   저 세개의 그래프를 다 그려보면 가운데 그은 직선이 점을 지날 때가 존재한다. (8,12) 마지막 점을 포함해보면
   $\frac{12}{8}x$는 4개, $\frac{6}{4}x$는 2개, $\frac{3}{2}x$는 1개이다. 이는 최대공약수의 값과 일치하는 것을 알 수 있다. w=8, h=12인 사각형을 4개의 점으로 나눠보면 w=2, h=3인 사각형이 4개 존재하는 것을 알 수 있다. 정리해보면, $X*gcd(W,H)$ 를 통해 접어진 사각형을 알 수있다.

2. 두번째 포인트 (X 구하기)
   약분을 하기 위해선 $w = \frac{W}{gcd(W,H)},h=\frac{H}{gcd(W,H)}$ 식을 이용한다. 이렇게 계산된 약분된 최소한의 크기의 직사각형에서 선이 그려지는걸 하나하나 생각해보면.
   w=2, h=3인 직사각형에서 w와 h를 하나씩 추가해가면서 선을 그려보면 맨 시작부분에서 한번 겹치고 w와 h가 하나씩 추가 될 때마다 접히는 사각형이 하나씩 추가된다. 수식으로는 직선이 지나는 갯수 $w +h -1$이 되며 이를 전체 크기의 사각형으로 생각해보면
   $X = \frac{W}{gcd(W,H)} + \frac{H}{gcd(W,H)} -1$ 이다.
   위 식에서 결과는 $X*gcd(W,H)$이므로 최종 정리하면
   $W+H-gcd(W,H)$ 공식을 통해 최종적으로 구할 수 있다.

되게 특이한 문제면서 재밌는 문제였다. 구현보다는 문제를 어떻게 수식을 표현할 수 있는지가 더 중요했던 문제였다.