[BaekJoon 2559번] 수열(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

[문제 풀이 사이트]

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일의 온도의 합이 최대가 되는 값을 출력한다.

[입출력 예]

입력	출력
10 2 3 -2 -4 -9 0 3 7 13 8 -3	21
10 5 3 -2 -4 -9 0 3 7 13 8 -3	31

[문제 풀이]

슬라이딩 윈도우 알고리즘을 사용하는 문제이다.
: 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다.
: 배열의 일정한 범위(고정된 범위)를 비교할 때 사용한다.

슬라이딩 윈도우 알고리즘이 투 포인터 알고리즘하고 비슷하다고 느낄 수 있지만..
투 포인터 알고리즘은 배열의 범위가 조건에 따라 가변적이라는 것과 변수 2개를 사용하여 값을 얻는다는 것이 다르다.


그래서 입출력예시2번을 예로 들어서 설명해보도록 하겠다.

우선 입력 받은 값들을 배열에 저장한다.

고정된 범위가 5이므로, 배열의 0번째 ~ 4번째 사이의 합을 구한다.
최댓값은 -12이고 고정된 범위 안에서 합은 -12이다.

배열을 1칸 이동한다.
고정된 범위가 5이므로 배열의 1번째 ~ 5번째 사이의 합을 구해야 한다.
합을 구하기 위해서는 Sum 값에서 맨 왼쪽 인덱스(0번)의 값 3을 빼주고 맨 오른쪽 인덱스(5번)의 값 3을 더해주면 된다.
최댓값은 -12이고 고정된 범위 안에서의 합은 -12이다.

배열을 1칸 이동한다.
고정된 범위가 5이므로 배열의 2번째 ~ 6번째 사이의 합을 구해야 한다.
합을 구하기 위해서 Sum 값에서 맨 왼쪽 인덱스(1번)의 값 -2을 빼주고 맨 오른쪽 인덱스(6번)의 값 7을 더해주면 된다.
이렇게 되면 최댓값은 -3이고, 고정된 범위 안에서의 합은 -3이다.

배열을 1칸 이동한다.
고정된 범위가 5이므로 배열의 3번째 ~ 7번째 사이의 합을 구해야 한다.
합을 구하기 위해서 Sum 값에서 맨 왼쪽 인덱스(2번)의 값 -4을 빼주고 맨 오른쪽 인덱스(7번)의 값 13을 더해주면 된다.
이렇게 되면 최댓값은 14이고, 고정된 범위 안에서의 합은 14이다.

배열을 1칸 이동한다.
고정된 범위가 5이므로 배열의 4번째 ~ 8번째 사이의 합을 구해야 한다.
합을 구하기 위해서 Sum 값에서 맨 왼쪽 인덱스(3번)의 값 -9을 빼주고 맨 오른쪽 인덱스(8번)의 값 8을 더해주면 된다.
이렇게 되면 최댓값은 31이고, 고정된 범위 안에서의 합은 31이다.

배열을 1칸 이동한다.
고정된 범위가 5이므로 배열의 5번째 ~ 9번째 사이의 합을 구해야 한다.
합을 구하기 위해서 Sum 값에서 맨 왼쪽 인덱스(4번)의 값 0을 빼주고 맨 오른쪽 인덱스(9번)의 값 -3을 더해주면 된다.
이렇게 되면 최댓값은 31이고, 고정된 범위 안에서의 합은 28이다.

이렇게
1. 항상 범위가 고정되어 있기 때문에 처음 인덱스가 0일 때부터 초기 합산 값을 구한다.
2. 배열을 1칸 이동한다.
3. 이전의 합에서 맨 왼쪽 인덱스 값을 빼주고 이동했을때의 맨 오른쪽 인덱스 값을 더한다.
➜ 최소한의 작업으로 배열의 고정된 범위내에서의 합을 구할 수 있다.
4. 최댓값은 max 함수를 통해서 최댓값을 구해주면 된다.

[최종 코드]

[GitHub]

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

#include <bits/stdc++.h>

using namespace std;
vector<int> v;

int calculateMax(int t) {
    int gSize = v.size();
    int maxValue = 0;
    for(int i = 0; i < t; ++i) {
        maxValue += v[i];
    }
    int result = maxValue;
    for(int i = t; i < gSize; ++i) {
        result += (v[i] - v[i - t]);
        maxValue = max(maxValue, result);
    }
    return maxValue;
}

int main(void) {
    int N, K; cin >> N >> K;
    for(int i = 0; i < N; ++i) {
        int n; cin >> n;
        v.emplace_back(n);
    }
    cout << calculateMax(K);
}