[BOJ 1912] 연속합

> 문제 출처

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

 

> 문제 설명

N개(1 ≤ N ≤ 100,000)의 정수(-1000 ≤ K ≤ 1000)로 이루어진 수열이 주어졌을 때, 연속된 몇 개의 수를 선택하여 구할 수 있는 합중 가장 큰 값을 구하는 문제.

 

> 접근 방법

전형적인 DP(Dynamic Programming)문제이다. 처음엔 나름 생각한다고 신박한 방법을 썼는데 생각해보니 수열을 입력받으면서 바로 처리가 가능한 문제였다.

i번째 원소가 입력될 때, x~i까지의 최대합(sum[i-1] + input[i])과 input[i]값 중 큰 값을 sum[i]에 담는다.

이 과정에서 max_sum을 갱신해주며 리턴한다.

시간 복잡도는 O(N)으로 생각된다.

 

> CODE

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

#review
https://ssyoon.tistory.com/18

#reference

*/
#include <iostream>
#include <vector>

using namespace std;

vector<int> max_sum;

int main(){
    int N;
    cin >> N;
    
    max_sum.resize(N+1);
    int Answer=max_sum[0]=-1000;

    for(int i=1;i<N+1;i++){
        int input;
        scanf("%d",&input);
        max_sum[i] = max(max_sum[i-1]+input,input);
        Answer = max(max_sum[i],Answer);
    }
    cout << Answer << endl;
}

 

 

SCPC2020 예선을 경험하면서 정말 많이 부족하다는 걸 느꼈다. 이제껏 Greedy, DP 등의 알고리즘 분류도 모르고 전략 없이 무턱대고 문제를 풀었는데 앞으로의 학습 방향을 설정할 수 있는 좋은 기회가 된 것 같다.

---

https://github.com/dongha-yoon/ProgrammingStudy - cont_sum.cpp