문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/62048

문제 정리

• 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다.
• 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
• 사용할 수 있는 정사각형의 개수?

문제 해결 방법

위의 그림을 보면 뭔가 반복되는 규칙이 보인다. 이 규칙을 파고 들어가면 해결책이 보이게 된다.

문제 해결 로직

1. 주어진 w, h를 같은 수로 더 이상 나눠질 수 없게 만들어야한다. 즉, 최대 공약수가 1이여야한다.
   • 이 때 최대 공약수를 사용해서 나누면 된다.
2. 최대 공약수를 사용해서 더 이상 나눌 수 없게 w, h를 만들고, 이 때 정사각형을 못 만드는 것들의 수를 구한다.
3. 못 만드는 것들의 수에다 다시 최대 공약수를 곱하면 전체 크기에서 못 만드는 것들의 수를 구할 수 있다.

사실 여기서 2번 로직이 어떻게 해야할지 좀 애매하다.

여기에도 규칙이 있다.

우선 몇 가지 그림을 그려보았다.

(3,2) 크기의 직사각형, (4,3) 크기의 직사각형, (5,4) 크기의 직사각형