[Algorithm #08] 2559 - 수열 (C++)

문제 설명

1. 정수 N와 K를 입력받는다.

• N은 온도를 측정한 전체 날짜의 수 K는 합를 구하기 위한 연속적인 날짜의 수

2. N 크기의 수열을 입력받는다.
3. K일 동안의 온도의 합 중에 최대합을 출력한다.

문제 해결 전략

1. 입력받는 N의 범위는 1 ~ 10만 K는 1 ~ 10만 - 1 (N 사이값이기 때문에 -1)
2. 연속된 온도의 합이 최대가 되는 값이기 때문에 구간합을 떠올리자
3. 최댓값을 구하라 ! -> 최솟값부터 최댓값까지 최솟값을 구하라 ! -> 최댓값부터 최솟값

• ret = max(ret,val) or ret = min(ret,val)

4. 이 문제의 최솟값은 -100 (들어오는 제일 작은 입력) * 10만번 >> -1000만
   즉, ret = -10000001; (넉넉하게 -987654321 사용해도 됩니다.)
5. ret를 미리 구한 psum배열(구간합)에서 꺼내서 max()로 갱신

#include <iostream>
#include <algorithm>

using namespace std;


int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    int tem[100000];
    int psum[100000] = {0,};
    int result = -10000001;
    cin >> N >> K;

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

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

    cout << result << "\n";

    return 0;
}

소감

연속된 온도의 합 -> 구간합이라는 생각을 맨 처음에 떠올리지 못했다.
왜냐면 이 문제를 풀 당시에 나는 거의 2달 전이라 잘 못했다. 어쨌든 구간합 prefix psum을 생각하면 굉장히 쉬운 문제. 맨 처음에 stack를 써서 풀었는데 당연히 시간초과가 발생했다.
주어진 입력과 조건을 보고 구현하자. 시간 날리지 말고.

틀린 Case

/**
 * Stack 사용
 */

vector<int> temperature;
vector<int> temp_temperature;
vector<int> result;

void return_push(int n) {
    int temp = 0;
    for (int i = 0; i < n; i++) {
        temp = temp_temperature.back();
        temperature.push_back(temp);
        temp_temperature.pop_back();
    }
}

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

    int N, K, x;
    int flag = 0;
    int temp_sum = 0;
    int temp;

    cin >> N >> K;

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

    while (!temperature.empty()) {
        temp_sum = 0;
        flag = 0;
        flag = K;
        while (flag--) {
            temp_sum += temperature.back();
            if (flag == K - 1)
                temperature.pop_back();
            else {
                temp_temperature.push_back(temperature.back());
                temperature.pop_back();
            }
        }
        return_push(K - 1);
        result.push_back(temp_sum);
    }
    cout << *max_element(result.begin(), result.end());
}

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