Softeer - 성적 평균

softeer.ai/practice/info.do?eventIdx=1&psProblemId=389

Softeer

나 때문에 문제의 정답률이 많이 내려갔을 것이다...

 

 

 

주어진 간격에 대한 평균을 구하는 알고리즘은 문제가 없었는데...

배열의 크기를 10^6 + 1 로 잡았어야 했는데 10^5 + 1으로 잡아 계속해서 틀렸던 문제...

이거 때문에 문의 드려볼까도 생각했었는데 정말 창피해질뻔 했다.

설마 내가 이걸 틀렸겠어?란 생각에 디버깅 과정에 제대로 보지도 않았다...

 

컴퓨터 비전을 공부해본 사람이라면 이 문제를 풀면서 적분 이미지(Integral Image)가 생각났을 것 같다. 실제로 구현은 해본적 없는데 아마 이 문제에서 요구하는 알고리즘을 2차원 데이터에 적용하는 게 아닐까 싶다.

 

* cout.precision(n); n+1번째 자리에서 반올림한 결과를 출력한다.

 

 

 

#include<iostream>
#include <iomanip>

using namespace std;

int main(int argc, char** argv)
{
        ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        cout.precision(2);
        cout << std::fixed;

        long long arr[1000001]={0,};
        long long cumulative_sum[1000001]={0,};
        long long N;
        long long K;

        cin >> N >> K;

        for(long long i=1; i<=N; i++)
        {
                cin>>arr[i];
                cumulative_sum[i] = cumulative_sum[i-1] + arr[i];
        }

        for(long long i=0; i<K; i++)
        {
                long long a, b;
                cin >> a >> b;
                double interval_avg = static_cast<double>((cumulative_sum[b]-cumulative_sum[a-1]))/(static_cast<double>(b-a)+1.);
                cout << interval_avg << '\n';
        }

        return 0;
}