728x90
연속합
https://www.acmicpc.net/problem/1912
<코드>
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 32 | #include <stdio.h> int main(void){ int N; int number[100010] = {}; int Dp[100010] = {}; int max; scanf("%d", &N); for (int i = 1; i <= N; i++) scanf("%d", &number[i]); for (int i = 1; i <= N; i++) { if (Dp[i - 1] + number[i] > number[i]){ Dp[i] = Dp[i - 1] + number[i]; } else { Dp[i] = number[i]; } } max = Dp[1]; for (int i = 2; i <= N; i++) if (max < Dp[i]) max = Dp[i]; printf("%d\n", max); } | cs |
<문제 푼 요령>
1. 이 문제는 최대값을 구하기 위해서는 현재의 자신의 값을 선택하는 경우의 수가 두가지이다.
2. 첫 번째 경우는 이전의 값을 더한것과 지금의 값을 더한 값이 최대일 때랑 이전의 값을 더하지 않고 현재의 값만이 최대일 때 이 두가지 경우만 따지면 된다.
728x90
'Algorithm > DP(동적 계획법)' 카테고리의 다른 글
[백준][1699번][DP] 제곱수의 합 (0) | 2016.04.14 |
---|---|
[백준][2579번][DP] 계단 오르기 (1) | 2016.04.14 |
[백준][11054번][DP] 가장 긴 바이토닉 부분 수열 (0) | 2016.04.14 |
[백준][11722번][DP] 가장 긴 감소하는 부분 수열 (0) | 2016.04.14 |
[백준][11055번][DP] 가장 큰 증가 부분 수열 (0) | 2016.04.14 |
댓글