[백준] 2559번 : 수열 (C++) - 실버 3

이 문제는 백준 알고리즘에서 제공하는 단계별 문제 풀이 중 '누적합' 단계에 해당한다.

 

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

[ 그림 1 ] 2559번 문제 전문

 

해당 문제는 하나의 배열에 누적합을 표현함으로써 구간별 합을 표현하는 방식에 대해 고민해보기 좋은 문제였다.

 

기본적으로 위와 같은 문제를 해결하는 원리는 부분 합의 시작 인덱스와 끝을 나타내는 변수 두 개를 선언하고, 각 구간별 합을 구한 뒤, 이전 구간의 합과 비교하여 더 큰 값을 누적합 저장 변수에 갱신하는 방향으로 진행된다.

 

방향성 자체는 이러하나, 사실 별도의 변수 두 개를 선언할 필요는 없다.

 

왜냐하면 일종의 포인터 역할을 하는 두 개의 변수를 별도로 선언하여 원초적으로 각 구간의 합을 매번 구하는 것과, 각 입력값에 대한 합의 결과를 매번 반복마다 배열에 먼저 저장하고, 특정된 두 지점의 값을 서로 빼어 해당 구간의 합을 구하는 방식 모두 같은 결과를 도출하기 때문이다.

 

오히려 후자의 경우가 특정 구간에서의 모든 원소에 대한 합을 매 반복마다 구하지 않아도 누적합 배열의 특정 인덱스의 원소에 바로 접근할 수 있기 때문에 결과를 도출하는 과정 또한 훨씬 단순해진다.

 

먼저 문제 조건이다.

1. 2 <= N <= 100000
2. 1 <= K <= N
3. -100 <= (둘째 줄의 수) <= 100

위의 조건에 맞게 변수 선언 및 초기화를 진행한다.

int N, K;
int accumulated_sum[100000];
int max_sum = -10000001;

 

누적합의 결과는 아무리 많아도 N의 최대 크기인 100000을 넘을 수 없으므로 누적합 배열을 의미하는 accumulated_sum 배열의 크기를 100000으로 초기화한다. 

 

누적합의 최소 결과는 N = 100000, K = 1, 둘째 줄의 수가 모두 -100인 -10000000보다 더 작을 수 없으므로 누적합 결과 저장 변수인 max_sum의 초기값을 -10000001로 초기화한다.

 

 

 

다음으로 누적합을 누적합 배열에 저장하는 코드이다.

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

누적합 배열인 accumulated_sum의 i번 째 인덱스에 바로 직전의 i - 1번 째 인덱스와 i번 째 입력값인 tmp의 합이 저장된다.

 

 

 

마지막으로 최대 누적합을 변수에 갱신하는 코드이다.

for (int i = K; i <= N; i++) {
    max_sum = max(max_sum, accumulated_sum[i] - accumulated_sum[i - K]);
}

기존의 최대 누적합과 현재의 누적합 계산 결과를 비교하여 둘 중 큰 값을 변수에 저장하게 된다.

 

max 함수의 경우 std 네임스페이스에 존재하는 내부 함수이기 때문에 별도의 라이브러리 호출 없이 사용 가능하다.

 

 

 

위의 코드를 병합하면 다음과 같다. 해당 코드에는 입출력 시간을 단축시켜주는 코드가 포함되어있다.

#include <iostream>

using namespace std;

void fast_io() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main() {
    fast_io();

    int N, K;
    int accumulated_sum[100000];
    int max_sum = -10000001;

    cin >> N >> K;

    for (int i = 1; i <= N; i++) {
        cout << i << '\n';
        int tmp;
        cin >> tmp;
        accumulated_sum[i] = accumulated_sum[i - 1] + tmp;
    }

    for (int i = K; i <= N; i++) {
        max_sum = max(max_sum, accumulated_sum[i] - accumulated_sum[i - K]);
    }
    cout << max_sum  << "\n";
}