2559번: 수열

2559번: 수열

사용 언어: C++

문제 요약

• 어떤 날마다 측정한 기온이 정수 수열로 주어진다.
• 이 중 연속된 K일 동안의 기온의 합 중에서 가장 큰 값을 구하라.

📌 입력

• 첫 줄: N K
  • N: 전체 날짜 수 (2 ≤ N ≤ 100,000)
  • K: 연속 날짜 수 (1 ≤ K ≤ N)
• 둘째 줄: N개의 정수 (각 날짜의 기온, -100 ~ 100)

📌 출력

• 연속된 K일 동안의 기온 합 중 최댓값

풀이

이 문제를 풀 때 두 가지가 대표적으로 떠오르는데,

1. 첫 번째는 그냥 누적합을 구하고 모든 길이의 구간에 대해서 누적합으로 계산해서 최대값을 비교하는 방법

2. 두 번째는 슬라이딩 윈도우다. 얘는 그냥 개별 인덱스를 사용하는건데 첫번째 구간 인덱스를 더해서 구하고 첫 번째 인덱스는 빼고 다음 인덱스 값을 더해 값을 비교하는 방식이다.

 

누적합 방식 코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<int> A(N + 1);
    vector<int> prefix(N + 1);

    cin >> A[0];
    prefix[0] = A[0];

    for (int i = 1; i < N; i++) {
        cin >> A[i];
        prefix[i] = prefix[i - 1] + A[i];
    }

    int maxSum = prefix[M - 1];
    for(int i=M; i<N; i++){
        maxSum = max(maxSum, prefix[i] - prefix[i-M]);
    }

    cout << maxSum << '\n';

    return 0;
}

 

슬라이딩 윈도우 코드

#include <iostream>
#include <vector>
using namespace std;

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

    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for (int i = 0; i < N; ++i)
        cin >> A[i];

    int sum = 0;
    for (int i = 0; i < M; ++i)
        sum += A[i];

    int maxSum = sum;

    // 슬라이딩 윈도우: 한 칸씩 이동하며 앞 요소 빼고 새 요소 더하기
    for (int i = M; i < N; ++i) {
        sum += A[i] - A[i - M];
        if (sum > maxSum)
            maxSum = sum;
    }

    cout << maxSum << '\n';
    return 0;
}