책 나누기 timer 1s memory - MB

명수는 새학기를 맞아 책장에 책을 정리하고자 한다. 명수가 사용하는 책장의 칸 수는 총 3칸이다. 어떤 방식으로 책을 책장에 꽂을 것인지 연구하던 명수는 다음과 같은 방법을 지킬 경우 미관상으로 예쁘게 책이 꽂히고, 공학적으로 최적임을 증명하였다. 어떻게 최적임을 증명하였는지 다들 궁금할 것이다. 하지만, 증명이 너무나 길기 때문에 본 문제에서는 이를 생략하도록 한다.

방법은 다음과 같다.

1. 3칸에 적어도 한개의 책을 꽂아야 한다. 2. 모든 책을 다 꽂았을 때, 책의 높이(h)와 두께(t)에 대해 다음 수식에 대해 가능한 경우 중 최소가 되어야 한다.

위 수식에서 hi는 i번 책의 높이, ti는 i번 책의 두께를 뜻한다. 또한 S1, S2, S3 은 각각 책장 1번칸, 2번칸, 그리고 3번 칸을 뜻하며 이는 책장에 꽂힌 책들의 번호의 집합으로 표현이 가능하다. 만약 S1 = { 1, 3 }, S2 = { 2, 4, 5 }, S3 = { 6 }일 경우 1번 칸에는 1번 3번 책이, 2번 칸에는 2, 4, 5번 책이, 3번 칸에는 6번 책이 꽂혀 있다는 것을 의미한다.

위 수식을 말로 풀어서 설명 하자면, ( S1, S2, S3 에서 각각 높이가 가장 높은 책들의 높이의 합 ) × ( S1, S2, S3 중 각 칸에 꽂힌 두께의 합이 가장 높은 칸의 두께의 합 )와 같은 의미이다.

책들의 높이와 두께가 주어졌을 때, 명수가 생각한 방법에 맞게 책을 꽂는 방법을 찾는 프로그램을 작성하라.