[C++] 백준 1912번 - 연속합

---

0. 문제

 

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

 

1. 아이디어

 

1) dp[i]에는 i번째 원소가 가지는 최대 연속합이다!!!

 

2) 연속합이 음수가 되지 않는 선에서는 계속해서 더해도 상관이 없다.

 

2. 소스코드

 

#include <iostream>
#include <algorithm>
int arr[100000];
int dp[100000];
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 0; i < N; i++)
        std::cin >> arr[i];
    int result = dp[0] = arr[0];
 
    for (int i = 1; i < N; i++)
    {
        int temp = dp[i - 1] + arr[i];
        dp[i] = std::max(temp, arr[i]);
    }
    for (int i = 0; i < N; i++)
        if (dp[i] > result) result = dp[i];
 
    std::cout << result;
}

 

3. 결과

 

 

4. 피드백

 

• (일단 전역변수로 배열을 선언하면 default로 0으로 초기화가 된다..)

• 아쉽다.. 거의 다 풀었는데 테스트 케이스도 다 맞는 거 같았는데 너무 답답해서 결국 도움을 얻었다.

• dp의 값으로 결정한 컨셉에 대해서 확실하게 지키자. 여기서는 i번째 원소가 가지는 최대 연속합이라는 컨셉을 정했는데도 불구하고 억지로 풀어보려고 하다가 오래 걸렸다... 그랬으면 진작에 끝났을 걸.

---