1421 나무꾼 이다솜

N개의 나무가 있고, 그 길이가 주어진다. 각 나무를 잘라서 모두 똑같은 길이로 만들어 주려고 한다. 길이 1당 가격과 한번 자를 때 드는 비용을 주었을 때, 최대 이익을 구하는 문제이다.

이 문제는 자르는 횟수를 구하는것이 중요하다. 예를들어 한 나무의 길이가 5이고, 길이를 2로 맞춰서 자른다면, 2번 자르고 남은 길이 1을 버려주면 된다. 얼핏보면 5 / 2 를 내림해주면 될 것 같지만, 나무의 길이가 4라면 1번만 자르면 된다. 몇번 해보면 확실해지지만 결론은
(길이 - 1) / 2 해준것이 잘라낸 횟수이다.

모든 나무의 길이 중 최대값을 찾아서 그 길이부터 1씩 감소시키면서  모든 나무에 대해 몇번 자르고, 얼마만큼 버려서 얼마를 획득할 수 있는가를 구한다. 모든 나무를 다돌면서 얻은 돈의 최대값을 구해주면 된다.

소스