[C++] 백준 2559번:수열

문제링크

2559번: 수열

문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 

3 -2 -4 -9 0 3 7 13 8 -3

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

이때, 온도의 합이 가장 큰 값은 21이다. 

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며, 

이때, 온도의 합이 가장 큰 값은 31이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다. 

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

 

풀이

슬라이딩윈도우 알고리즘을 사용하여 풀이하였다.

입력 받은 온도를 배열에 넣어주고 index가 마지막일 때까지 window_sum에 index에 위치한 값을 더해준다.

만약 위에서 index가 K-1보다 크거나 같다면 최대 값을 비교하여 갱신한다. 또한 연속된 합에서 가장 앞에 위치한 부분의 값을 빼주고, 가장 앞에 위치한 index를 +1 해주도록 한다.

위 내용이 잘 이해가 가지 않는다면 아래 링크로 들어가 슬라이딩 윈도우에 대해 조금 읽어보시면 도움이 되실 것 같습니다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, k;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> k;
 
    vector<int> temperature(n);
    for (int i = 0; i < n; i++) {
        cin >> temperature[i];
    }
 
 
    int startNum = 0;
    int window_sum = 0;
    int max_sum = -100000000;
 
    for (int end = 0; end < n; end++) {
        window_sum = window_sum + temperature[end];
 
        if (end >= (k - 1)) {
            max_sum = max(max_sum, window_sum);
            window_sum = window_sum - temperature[startNum];
            startNum++;
        }
    }
 
    cout << max_sum;
}

 

메모