문제
On each move, choose one rectangle and cut all the way across it, parallel to a side, making two rectangles with positive integer side lengths. Continue until every piece is a square. Squares may have different sizes. Count cuts, not pieces.
Implement rectangle_cutting(height, width).
Input
height: The starting rectangle height.
width: The starting rectangle width.
Output
Return the minimum number of cuts.
제약 조건
1 ≤ height, width ≤ 500. Rotation does not change the answer.
예시
입력:
width = 3
height = 2
예상 출력:
expected = 2입력:
long long width = 3;
long long height = 2;
예상 출력:
long long expected = 2;입력:
long width = 3;
long height = 2;
예상 출력:
long expected = 2;설명
Cut off a 2 × 2 square, leaving a 2 × 1 rectangle. One more cut splits the remainder into two unit squares.
입력:
width = 4
height = 4
예상 출력:
expected = 0입력:
long long width = 4;
long long height = 4;
예상 출력:
long long expected = 0;입력:
long width = 4;
long height = 4;
예상 출력:
long expected = 0;설명
The starting rectangle is already a square.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
A rectangle can be solved by splitting it into two smaller rectangles and combining their best answers.
힌트 2
Try every possible horizontal and vertical cut to find the minimum.
힌트 3
Memoization or a table is helpful because many subrectangles repeat.
예상 복잡도
O(h*w*(h+w)) time, O(h*w) extra space
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.