[코딩 테스트] 소프티어 연습 문제 - 성적평균 (C++)

소프티어 성적평균 문제를 풀어보았습니다.

 

소프티어 연습 문제 - 성적평균 (C++)

 

https://softeer.ai/practice/info.do?idx=1&eid=389&sw_prbl_sbms_sn=249449

Softeer

 

 

 문제 

 

N명의 학생들의 성적이 학번순서대로 주어졌다.

학번 구간 [A, B]가 주어졌을 때 이 학생들 성적의 평균을 구하는 프로그램을 작성하라.

 

 

제약조건

 

1 ≤ N ≤ 10의 6 제곱인 정수

1 ≤ K ≤ 10의 4 제곱인 정수

1 ≤ Si ≤ 100 인 정수

1 ≤ Ai ≤ Bi ≤ N

 

입출력 예제

 

입력예제1

5 3
10 50 20 70 100
1 3
3 4
1 5

출력예제1

26.67
45.00
50.00

 

문제 설명 및 코드

 

일단 보자마자 가장 눈에 들어오는 것이 N과 K의 크기였습니다. 10의 6 제곱과 10의 4 제곱이라면 N제곱은 힘든 시간복잡도를 가질 것입니다. 따라서  N을 최대한 N번만 돌리고 K번 확인하는 것이 최적이라고 생각했습니다.

결국 입력을 받으면서 부분합 배열에 저장해 놓고 계산하면 되는 생각보다 간단한 문제였습니다.

#include<iostream>
#include<vector>

using namespace std;
int N, K;
#define MAX_N 1000001

int main(int argc, char** argv)
{
    cin >> N;
    cin >> K;
    int sum_table[MAX_N];
    int score = 0;
    sum_table[0] = 0;

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

    vector<double> results;
    int start, end;
    int diff, sum = 0;
    for(int j = 0; j < K;j++) {
        cin >> start;
        cin >> end;
        results.push_back((double)(sum_table[end] - sum_table[start-1])/(end - start + 1));
    }

    for(const auto& it:results) {
        printf("%.2f\n",it);
    }

	return 0;
}

 

 결론

 

level3 치곤 굉장히 간단한 문제였습니다. 만약 부분합 배열의 개념을 몰랐다면 어려웠을 수도 있지만 이제는 흔한 개념이어서 상대적으로 쉬운 문지였던 것 같습니다.