Time Limit: 1s
Memory Limit: 128MB
15.1을 참조하여, rod cutting problem을 dynamic-programming algorithm으로 해결하여 optimal value(maximum revenue)와 optimal solution을 구하시오.
*optimal value를 만드는 솔루션이 단 하나만 나오도록 test sample을 설계했으므로 중복 정답은 고려하지 않아도 됨.
예를 들어, 아래의 sample은 79가 optimal value이며, 이때의 optimal solution은 길이 1짜리 1개, 길이 3짜리 3개임. 해당 솔루션을 제외하고 79를 만드는 solution이 없으며 코드 검사에 사용되는 다른 test case들도 이와 같이 단 하나의 솔루션만을 가지고 있음.
* 정답 반환 시 optimal value와 optimal solution을 출력해야함. 첫 번 째 줄에서는 optimal value를 출력함. 이후 다음 줄에서부터 길이에 대한 오름차순으로 한 줄 씩 rod 길이를 출력하되 같은 길이의 rod가 여러 개 필요한 경우 그 개수만큼 반복 출력함.
예를 들어, 아래의 sample에서는 optimal value인 79를 먼저 출력함. 이에 대한 솔루션이 '길이 1짜리 1개, 길이 3짜리 3개'이므로 다음과 같이 출력함
1
3
3
3
Line 1: n
Line 2: p[1]
Line 3: p[2]
...
Line n+1: p[n]
* n : length of rod, 1 < n <= 10
* array p : price table
Line 1: optimal value(maximum revenue)
Line 2 : the optimal solution
10 7 15 24 30 39 42 46 55 63 67
79 1 3 3 3