직사각형을 정사각형으로 자르기

문제

각 단계마다 하나의 직사각형을 선택하여 한 변에 평행하게 끝까지 자릅니다. 이때 두 개의 양의 정수 길이의 직사각형이 만들어집니다. 모든 조각이 정사각형이 될 때까지 반복합니다. 정사각형의 크기는 서로 달라도 됩니다. 조각의 개수가 아니라 자른 횟수를 세세요.

rectangle_cutting(height, width)를 구현하세요.

height: 시작 직사각형의 높이입니다.

width: 시작 직사각형의 너비입니다.

최소 자르기 횟수를 반환하세요.

1 ≤ height, width ≤ 500. 회전해도 답은 변하지 않습니다.

예시 1

입력:
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;

2 × 2 정사각형을 잘라내면 2 × 1 직사각형이 남습니다. 한 번 더 자르면 나머지가 두 개의 1 × 1 정사각형으로 나뉩니다.

예시 2

입력:
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;

시작하는 직사각형이 이미 정사각형입니다.

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

직사각형은 두 개의 더 작은 직사각형으로 나누고, 그 최적 답을 합쳐서 풀 수 있다.

힌트 2

가로와 세로의 모든 가능한 절단선을 시도해 최소값을 찾는다.

힌트 3

많은 부분 직사각형이 반복되므로 메모이제이션이나 테이블이 유용하다.

예상 복잡도

시간 O(h*w*(h+w)), 추가 공간 O(h*w)

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.