[백준(BOJ) 15460번] My Cow Ate My Homework 풀이

문제 : https://www.acmicpc.net/problem/15460

 

s[0...n-1]에 주어진 score를 저장합시다.

이 문제는 k를 1부터 n-2까지 증가시키며, s[k]...s[n-1] 중 최솟값을 제외한 것의 평균을 최대로 하는 k들을 구하는 문제입니다.

 

최대 n이 100,000이므로 O(n^2)이 되면 안되는데, 다음과 같이 O(n)에 score의 부분합과 부분최솟값을 미리 구해놓으면 나중에 s[k]...s[n-1] 중 최솟값을 제외한 것의 평균을 O(1)에 구할 수 있습니다.

 

a[i] : s[n-1]부터 s[i]까지 합.

m[i] : s[n-1]부터 s[i]까지 최솟값.

 

그 다음부터는 k를 1부터 n-2까지 증가시키며, a[k] - m[k] / (n - k - 1)이 최대가 되는 k들을 출력하면 됩니다.

 

그런데, a[k] - m[k] / (n - k - 1)은 실수 형태이기 때문에 여러 k가 같은 최댓값을 가지는 지 비교할 때 오차가 생길 수 있습니다. 우리는 이 값을 최대로 하는 a[k] - m[k]와 n - k - 1을 따로 저장하면서 비교하면 이 문제를 해결할 수 있습니다.

 

중간에 int 범위를 초과할 수 있는 연산이 있으므로 long long을 쓰면 됩니다.

#include <iostream>
#include <vector>

using namespace std;

int n;
int s[100000];
int a[100000];  // accumulated sum from back
int m[100000];  // min from back

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

    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];

    a[n - 1] = m[n - 1] = s[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        a[i] = a[i + 1] + s[i];
        m[i] = min(s[i], m[i + 1]);
    }

    pair<int, int> max_avg = {0, 1};  // {sum, cnt}
    for (int k = 1; k < n - 1; k++) {
        // a[k] - m[k] / (n - k - 1) > max_avg
        if ((long long) (a[k] - m[k]) * max_avg.second > (long long) max_avg.first * (n - k - 1))
            max_avg.first = a[k] - m[k], max_avg.second = n - k - 1;
    }

    for (int k = 1; k < n - 1; k++) {
        // a[k] - m[k] / (n - k - 1) == max_avg
        if ((long long) (a[k] - m[k]) * max_avg.second == (long long) max_avg.first * (n - k - 1))
            cout << k << '\n';
    }

    return 0;
}