문제
길이가 N인 막대기가 있다. 막대기를 길이가 자연수가 되도록 여러 조각으로 자를 수 있다. 각 길이에 대해 값어치가 있을 때, 값어치 합이 최대가 되도록 막대기를 자르자.
예를 들어, 길이가 4인 막대기가 있고 각 길이 별 값어치가 아래와 같다고 하자.
| length | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| cost | 1 | 5 | 8 | 9 |
이 때, 길이 2인 막대기가 두 개가 되도록 전체 막대기를 자를 경우 전체 값어치가 10 되어 최대가 된다.
입력
첫 줄에 막대기의 길이 N이 주어진다. (1≤N≤3,000)
둘째 줄에 N개의 자연수가 공백으로 구분되어 주어지는데, i번째로 주어지는 수는 길이가 i인 막대기의 값어치를 의미한다. 이 때 주어지는 수는 1,000를 넘지 않는다.
출력
첫 줄에 값어치 합이 최대가 되도록 막대기를 자를 때, 값어치 합을 출력한다.
힌트
예제 입력
4
1 5 8 9
예제 출력
10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | <span style="font-family: "맑은 고딕", sans-serif;"> #include <iostream>/* run this program using the console pauser or add your own getch, system("pause") or input loop */ int main(int argc, char** argv) { int N; //막대기의 개수 int cost[3000]; scanf("%d", &N); for(int i=0; i<N; i++){ scanf("%d", &cost[i]); } int profit[3000]; profit[0] = cost[0]; int maxProfit = 0; int curProfit = 0; for(int i=1; i<N; i++){ maxProfit = cost[i]; for(int k=0; k<i; k++){ curProfit = profit[k] + cost[i-k-1]; if(curProfit > maxProfit){ maxProfit = curProfit; } } profit[i] = maxProfit; } printf("%d", profit[N-1]);} </span> |
