백준 2559 - 수열

백준 2559 문제 바로가기

풀이

길이가 N인 정수 배열이 주어졌을 때, 연속된 K개의 합이 가장 큰 경우를 구하는 문제이다.

2 <= N <= 100,000, 1 <= K <= N이므로 이중 for문을 사용하여 모든 경우를 일일이 구하면, 시간 제한(1초) 내에 수행될 수 없다.

‘투 포인터’라고 불리는 알고리즘을 사용하면 되는데, 조금 쉽게 생각해보면 어떤 K개의 연속합을 구했다면 그 다음 K개의 연속합을 구하기 위해서 처음 위치(left)의 값을 빼고 다음 위치(right)의 값을 더하여 구할 수 있다.

N = 5, K = 3인 예제를 보면 대략 이런 형태이다.

O를 K개의 연속합을 구하는 위치라고 했을 때

OOOXX (이때의 합은 sum이다. left = 0, right = 2)

XOOOX (left = 1, right = 3)

즉, 새로운 sum을 구하기 위해 K번을 반복할 필요 없이 좌우 끝값만 갱신해주면 된다.

sum -= temperature[left];
sum += temperature[right];

주의할 점

maxSum을 0으로 초기화하면 N개의 수가 모두 음수로만 주어졌을 경우에 답은 음수가 되는데, 항상 음수 < 0이므로 maxSum이 갱신되지 않아 올바른 정답을 출력할 수 없으니 주의한다.

소스 코드

#include <iostream>
using namespace std;


int N, K;
int temperature[100001];
int maxSum = 1 << 31;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    cin >> N >> K;
    for (int i = 0; i < N; ++i) {
        cin >> temperature[i];
    }

    int sum = 0;
    for (int i = 0; i < K; ++i) {
        sum += temperature[i];
    }
    if (maxSum < sum)
        maxSum = sum;

    for (int left = 0, right = K; right < N; ++left, ++right) {
        sum -= temperature[left];
        sum += temperature[right];
        if (maxSum < sum)
            maxSum = sum;
    }
    cout << maxSum;
    return 0;
}