BOJ

백준 1912 - 연속합

yanJuicy 2019. 5. 7. 00:12
반응형

문제

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

 

1912번: 연속합

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

 

풀이

연속된 수열 중 최대 값을 찾아야 하는 문제이다.

 

수열을 처음부터 차례로 더하면서 더한 결과가 0보다 크면 우선순위 큐에 저장을 한다. 만약 더한 결과가 0보다 작으면 그 수열 조합은 최대값이 될 수 없으므로, 그 다음 값 부터 수열을 시작해서 다시 최대값을 찾는다.

 

만약 우선순위 큐가 비었다면 배열에는 0보다 큰 값이 없는 것이다. 따라서 배열을 내림차순으로 정렬하면 된다.

 

 

코드

c++

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    vector<int> v;
    while (n--)
    {
        int num;
        cin >> num;
        v.push_back(num);
    }
 
    priority_queue<int> pq;
 
    int result = 0;
    for (int i = 0; i < v.size(); i++)
    {
        if ((v[i] < 0&& (result + v[i] < 0))
        {
            result = 0;
            continue;
        }
 
        result += v[i];
        pq.push(result);
    }
 
    if (pq.empty())
    {
        sort(v.begin(), v.end(), greater<int>());
        cout << v[0];
    }
    else
        cout << pq.top();
 
    return 0;
}
 
cs

 

반응형

'BOJ' 카테고리의 다른 글

백준 1463 - 1로 만들기  (0) 2019.05.12
백준 3085 - 사탕 게임  (0) 2019.05.12
백준 1969 - DNA  (0) 2019.04.10
백준 2217 - 로프  (0) 2019.04.10
백준 1449 - 수리공 항승  (0) 2019.04.09