문제
m * n 크기의 나무판이 있습니다. 무사(武士)의 후손인 영찬이는 이 나무판을 자르고 싶어합니다.
조상으로부터 대대로 내려온 장미문양 식칼을 든 영찬이는 다음 규칙에 맞추어 칼질을 정확히 k번 할 것입니다.
- 모든 칼질은 수평 또는 수직이어야 합니다.
- 모든 칼질은 격자점을 지나야 합니다. 즉, 1*1 짜리 나무판 조각을 자를 수 없습니다.
- 영찬이는 손이 빠르기 때문에, 모든 칼질은 한꺼번에 이루어집니다.
즉, 나무판이 가로로 잘려 두 조각이 되었다고 하더라도, 세로로 그들을 한꺼번에 자를 수 있습니다.
위 그림은 5*6 크기의 나무판을 가로로 두 번, 세로로 세 번 총 5번 자른 예시입니다.
영찬이는 가장 작은 조각을 가능한 한 크게 하고 싶어합니다. 그 넓이를 구해 보세요.
입력
- 첫 번째 줄에 나무판의 가로 크기, 세로 크기와 칼질 횟수인 m, n, k가 차례대로 주어집니다.
출력
가장 작은 조각의 최대 크기를 출력합니다.
- 데이터의 30%는 m, n, k ≤ 1,000
- 나머지 70%는 m, n, k ≤ 2,000,000,000
- 모든 데이터에 대해 k ≤ m + n - 2
예제
5 6 2
10
출처
codeforces.com problem 449 A
로그인해야 코드를 작성할 수 있어요.