TIL 46일차_알고리즘문제_잘린 사각형의 개수

프로그래머스 문제중 "멀쩡한 사각형" 문제의 내용이다.
너비가w 높이가h인 사각형을 대각선으로 접었을 때, 잘린 사각형의 개수를 구하면 해결할 수 있는 문제다.

잘린 사각형의 개수

w가 8, h가12인 사각형이 있다.

이때, 직선이 지나는 점의 개수(빨간 사각형의 개수)는 4개이다.
이는 8과 12의 최대공약수이다.

최대공약수가 1일때를 생각해보자.
w가 2, h가 3일 때를 한번 살펴보자.
대각선이 점에 도착할때까지, 가로의 개수 + 세로의 개수만큼 사각형이 갈라진다.

다만, 위의그림에서 대각선이 점에서 시작할 때, 잘리는 사각형이 중복되므로 1을 빼줘야한다.
정리하면, 최대공약수가 1일때 잘라지는 사각형의 개수는 w+h-1이다.

그렇다면 최대공약수가 g일때는??
앞서 말했듯이, 중복되는 사각형은 대각선이 점을 지날때 생긴다.
따라서 최대공약수가 g일때는, 대각선이 점을 g번 지나므로
최대공약수가 g일때 잘라지는 사각형의 개수는 w+h-g이다.

참고:슈퍼짱짱