케이크 자르기
시간 제한1초메모리 제한128 MB
w 곱하기 h 직사각형을 m개의 축에 나란한 정수 직사각형으로 자르되, 가장 큰 조각의 넓이를 최소로 만든다.
문제
정수 크기 인 직사각형 케이크가 주어진다. 이 케이크를 정수 크기의 직사각형 조각 개로 나누되, 가장 큰 조각의 넓이가 최소가 되도록 하려고 한다. 모든 절단은 케이크의 한 변과 평행한 직선이어야 하며, 하나의 조각을 넓이가 양수인 두 조각으로 나눈다. 한 번의 절단은 오직 한 조각만 둘로 나누므로, 케이크를 조각으로 나누려면 정확히 번 잘라야 한다.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 공백 하나로 구분된 세 정수 , , 으로 이루어진 한 줄이며, 이고 이다. 인 줄은 입력의 끝을 나타내며 처리하지 않는다.
출력
각 테스트 케이스마다 가장 큰 조각의 최소 넓이를 나타내는 양의 정수 하나를 한 줄에 출력한다.
힌트
, , 일 때, 다음과 같이 자르면 가장 큰 조각의 넓이가 최소가 된다:
반면 , , 일 때는 다음과 같이 자르는 것이 최적이다:
