문제
정올이는 N * M 개의 유닛들로 구성된 직사각형의 초콜릿 바를 가지고 있다.
정올이는 정확하게 K개의 유닛들을 먹고 싶기 때문에 초콜릿 바를 나누어야 할 수도 있다.
정올이는 초콜릿 바를 나눌 때 유닛과 유닛 사이의 가로선 또는 세로선을 따라서만 나눈다.
따라서 초콜릿 바는 한 번에 두개 직사각형 조각으로 나누어진다.
예를 들어
2 * 3크기의 초콜릿 바를 가로로 나누면 1 * 3 크기 초콜릿 바 2개를 얻는다.
이때 비용은 잘린 길이의 제곱만큼 소요되므로 32 = 9가 된다.
2 * 3크기의 초콜릿 바를 세로로 나누면 2 * 1과 2 * 2 두 조각을 얻고
이때 비용은 22 = 4 이다.
초콜릿 바의 높이 N과 너비 M 그리고 먹고싶은 유닛의 개수 K가 주어질 때,
최소비용을 구하는 프로그램을 작성하시오.
1 ≤ N, M ≤ 30, 1 ≤ K ≤ min(N * M, 50)
입력
첫 행에 테스트 케이스의 수 T가 주어진다. (1 <= T <= 40910)
두 번째 행부터 행단위로 각 테스트 케이스가 주어진다.
각 테스트 케이스는 N, M, K 세 수로 구성된다.
1 ≤ N, M ≤ 30, 1 ≤ K ≤ min(N * M, 50)
출력
각 케이스에 대한 답을 행으로 구분하여 출력한다.
예제
4
2 2 1
2 2 3
2 2 2
2 2 4
5
5
4
0
출처
codeforces 598 E
로그인해야 코드를 작성할 수 있어요.