크기가 인 직사각형이 있다.
이 직사각형을 여러 개의 정사각형 타일로 빈틈없이 채우려고 한다. 정사각형 타일은 다음과 같이 구매할 수 있다.
직사각형 전체를 정사각형 타일들로 빈틈없이 채울 때, 필요한 비용의 최솟값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
필요한 비용의 최솟값을 출력한다.
한 변의 길이가 인 정사각형 타일 개를 사용하면 비용은 이다. 하지만 이것이 최적은 아니다.
대신 한 변의 길이가 인 정사각형 타일 하나와 한 변의 길이가 인 정사각형 타일 두 개로 채우면 비용은 이며, 이것이 최소 비용임을 보일 수 있다.
| 3 | 27 | . |
| 4 | 43 | 추가적인 제약 조건이 없다. |
