모든 챌린지
어려움 1명 해결 정답률 100.0%

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

오직 정사각형만 남도록 최소한의 직선 자르기 횟수를 구하세요.

배우게 될 내용

  • 너비와 높이로 DP 표 정의하기
  • 모든 가로세로 자르기 시도하기
  • 더 작은 직사각형의 결과 재사용하기

문제

원문 보기 (영어)

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

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

입력

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

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

출력

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

제약 조건

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

예시

예시 1
입력:
height = 2
width = 3

예상 출력:
expected = 2
입력:
long long height = 2;
long long width = 3;

예상 출력:
long long expected = 2;
입력:
long height = 2;
long width = 3;

예상 출력:
long expected = 2;

설명

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

예시 2
입력:
height = 4
width = 4

예상 출력:
expected = 0
입력:
long long height = 4;
long long width = 4;

예상 출력:
long long expected = 0;
입력:
long height = 4;
long width = 4;

예상 출력:
long expected = 0;

설명

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

접근 방법

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

힌트 1

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

힌트 2

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

힌트 3

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

예상 복잡도

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

참고 자료

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

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

# 코더 언어 시간 메모리 AI 평가 풀이
1 ННикита Python 954 ms - 4/5 코드 보기

다른 사람의 풀이 보기

커뮤니티 솔루션

스포일러: 아래에 1개 전체 솔루션 있음 먼저 직접 풀어보세요. 다른 개발자의 코드와 AI 리뷰도 참고할 수 있습니다. 로그인하고 문제를 풀면 토론에 참여할 수 있습니다.