[PS] 백준 2559 수열

이번에는 백준 2559번 수열 문제를 풀어보았습니다.

이 문제는 주어진 온도 수열에서, 연속된 K일 동안의 온도 합 중 가장 큰 값을 구하는 문제입니다.

연속 구간을 하나씩 확인하면서 합을 계산하고, 그중 최댓값을 갱신하는 방식으로 정리했습니다.

문제 설명

매일 측정한 온도가 정수 수열로 주어집니다.

이때 연속적인 K일 동안의 온도 합 중 가장 큰 값을 출력하면 됩니다.

예를 들어 10일 동안의 온도가 주어졌을 때,

연속된 3일 구간의 합들을 모두 구해보고 그중 최댓값을 찾는 방식입니다.

풀이 아이디어

연속된 K개의 구간을 왼쪽부터 하나씩 확인하면서 합을 계산하면 됩니다.

예를 들어 시작 인덱스를 i라고 하면,

• arr[i]
• arr[i+1]
• …
• arr[i+K-1]

까지의 합을 구하고,

이 값을 현재 최댓값과 비교해서 더 크면 갱신합니다.

즉, 가능한 모든 연속 구간의 합을 계산하면서 최댓값을 찾는 방식입니다.

코드

#include <bits/stdc++.h>
using namespace std;

int N;
int conti;
vector<int> arr;
int max_val = INT_MIN;

void solve() {
    for (int i = 0; i < N - conti + 1; i++) {
        int sum = 0;
        for (int j = i; j < i + conti; j++) {
            sum += arr[j];
        }
        if (sum > max_val)
            max_val = sum;
    }
}

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

    cin >> N;
    cin >> conti;

    for (int i = 0; i < N; i++) {
        int temp;
        cin >> temp;
        arr.push_back(temp);
    }

    solve();

    cout << max_val << endl;
    return 0;
}

풀이 흐름

1. 전체 날짜 수 N과 연속 구간 길이 K(conti)를 입력받는다.
2. 온도 수열을 배열에 저장한다.
3. 시작 위치를 하나씩 옮기면서 길이 K인 구간의 합을 구한다.
4. 구한 합이 현재 최댓값보다 크면 갱신한다.
5. 모든 구간을 확인한 뒤 최댓값을 출력한다.

구현 포인트

1. 최댓값 초기화는 INT_MIN 사용

온도는 음수도 들어올 수 있기 때문에, 최댓값을 0으로 두면 올바르지 않을 수 있습니다.

그래서 초기값은 int형에서 가장 작은 값인 INT_MIN으로 두었습니다.

int max_val = INT_MIN;

2. 가능한 모든 연속 구간 확인

길이가 K인 구간은 총 N - K + 1개가 가능합니다.

그래서 바깥 반복문은 다음 범위로 돌았습니다.

for (int i = 0; i < N - conti + 1; i++)

이렇게 하면 시작 위치를 하나씩 옮기면서 모든 연속 구간을 확인할 수 있습니다.

3. 반복문으로 합을 구하고 최댓값 갱신

각 구간마다 합을 새로 계산한 뒤, 최댓값과 비교해서 갱신하는 흐름입니다.

int sum = 0;
for (int j = i; j < i + conti; j++) {
    sum += arr[j];
}
if (sum > max_val)
    max_val = sum;