[Baekjoon(백준)][2559번] 수열(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "수열" 문제를 해결하는 방법에 대해 설명하려고 합니다. "수열" 문제는 일정 기간 동안 측정된 온도가 수열로 주어졌을 때, 연속된 일수의 온도 합이 최대가 되는 값을 찾는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

2559번: 수열

문제 개요

일정 기간 동안 측정된 온도가 수열로 주어졌을 때, 연속된 일수의 온도 합이 최대가 되는 값을 찾는 문제입니다. 주어진 수열에서 연속된 K일 동안의 온도 합이 최대가 되는 경우를 찾아 그 합을 출력해야 합니다.

해결 방법

이 문제는 누적 합(Prefix Sum)을 사용하여 효율적으로 해결할 수 있습니다. 먼저, 각 날짜까지의 온도의 누적 합을 계산한 후, 각 위치에서 K일 전의 누적 합을 빼 연속된 K일 동안의 온도 합을 구합니다. 이를 통해 모든 가능한 연속된 K일의 온도 합을 구하고, 그 중 최대값을 찾습니다.

코드 구현

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n = 0; // 전체 날짜 수
    cin >> n;
    int k = 0; // 연속된 날짜 수
    cin >> k;
    int temp = 0; // 각 날짜의 온도를 입력 받기 위한 변수
    vector<int> pres(n + 1, 0); // 누적 합을 저장할 벡터, 인덱스를 1부터 사용하기 위해 n+1 크기 할당

    // 누적 합 계산
    for (int i = 1; i <= n; i++) {
        cin >> temp;
        pres[i] = pres[i - 1] + temp; // 이전까지의 누적 합에 현재 온도를 더함
    }

    int max = -10000009; // 최대 온도 합 초기값, 문제의 조건에 따라 충분히 작은 값으로 설정
    // 모든 가능한 연속된 K일의 온도 합 계산
    for (int i = k; i <= n; i++) {
        int com = pres[i] - pres[i - k]; // i일까지의 누적 합에서 i-k일까지의 누적 합을 빼 연속된 K일의 온도 합을 구함
        if (max < com){
            max = com; // 최대 온도 합 갱신
        }
    }
    cout << max << "\n"; // 최대 온도 합 출력
}

코드 설명

본 코드는 먼저 전체 날짜 수와 연속된 날짜 수를 입력받은 후, 각 날짜의 온도 정보를 입력받아 누적 합을 계산합니다. 이후 모든 가능한 연속된 K일의 온도 합을 계산하여 최대 온도 합을 찾고, 이를 출력합니다.

결론

"수열" 문제는 누적 합(Prefix Sum)을 활용하여 효율적으로 해결할 수 있는 문제입니다. 이 방법은 연속된 구간의 합을 빠르게 계산할 필요가 있는 다양한 문제에 활용될 수 있습니다.