[백준 BOJ][DP] 1912 연속합

1912_연속합

 

링크

https://www.acmicpc.net/problem/1912

 

풀이

 

간단하게 풀 수 있는 문제입니다.

우선 가장 큰 값을 구해야 하기 때문에 max를 선언합니다. 연속합의 최댓값의 최솟값(-1000)-1로 초기화 합니다.

 

DP 배열에 값을 입력 받고, i=1부터 n까지 for문을 돌립니다.

그리고 DP[i] = MAX(DP[i], DP[i-1] + DP[i])를 해줍니다.

굳이 전의 연속합과 더한 것보다 이번 숫자가 크면 더할 필요가 없기 때문입니다.

연속해서 더한 게 크다면 더해야죠.

 

대신에 그 다음 라인에

max = MAX(max, DP[n])로 max 값을 구해주는 일도 잊지 말아야 합니다.

 

 

코드

 

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

//1912_연속합 #include <iostream> using namespace std;   int DP[100001];   int MAX(int a, int b){     return a > b ? a : b; }   int main(){     int n, max = -1001;     int i;       cin >> n;       for (i = 1; i <= n; ++i){         cin >> DP[i];         DP[i] = MAX(DP[i], DP[i] + DP[i - 1]);         max = MAX(max, DP[i]);     }       cout << max << endl;       return 0; } Colored by Color Scripter

cs