[2559번] 수열

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Queue 이용

2. 연속된 수의 합 처리 알고리즘

3. 음수로만 이루어 진 경우

이 문제는 큐를 이용하면 쉽게 해결 할 수 있다.

물론 배열을 이용해서 문제를 해결해도 되지만, 큐를 이용하면 최적의 메모리를 이용할 수 있는 장점이 있다.

Queue에 값을 push하면서 Queue에 값의 크기가 연속된 수의 크기와 같아지면 그때부터 알고리즘이 동작한다.

예를들어 1 2 3 4라는 나열된 수가 있고, 2개의 연속된 수를 체크한다 하면

큐에는 1이 push되고 그다음 2가 push될 때, 알고리즘이 동작하여 max값에 3이 들어가고, 

큐에 있던 1이 빠져나간 뒤, 3이 들어간다. (현재 큐에는 2, 3이 존재) 그리고는 3보단 5가 크니 max에 5가 들어가고

이 과정을 반복하는 알고리즘이다.

모든 값이 음수인 경우도 생각해주어 똑같은 방식으로 짜주면 된다.

소스 코드 : 

#include <iostream>
#include <queue>
 
using namespace std;
 
int main()
{
    queue<int> q;
 
    int n, cnt;
    int val;
    int sum = 0,max = -1;
    int minSum = 0;
 
    cin >> n;
    cin >> cnt;
 
    for (int i = 0; i < n; i++)
    {
        cin >> val;
        q.push(val);
 
        sum += val;
        if (q.size() == cnt)
        {
            if (sum > max)
                max = sum;
            
            if (sum < max)
                minSum = sum;
 
            sum -= q.front();
            q.pop();
        }
    }
 
    
    printf("%d", max != -1 ? max : minSum);
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>