뚝딱뚝딱

소프티어에 있는 lv3 연습 문제 "성적 평균"에 대한 풀이 방법이다.

풀이 날짜는 2023.11.01로, 최근에 소프티어 페이지가 리뉴얼 되었다.

그런데 리뉴얼 후 문제인지, 아니면 이렇게 업데이트 된 것인지 모르겠는데..

어제 다른 문제를 풀 때, 답이 틀리면, 제출 이력에 틀린 답도 뜨고, 왜 틀렸는지(그 문제의 경우 시간초과였음) 표시도 되어있었다.

그런데 오늘 아침부터 풀고 있던 이문제.. 문제 자체에만 틀렸다고 표시되어 있고, 내가 제출한 이력은 전혀 보이지 않는다.

분명 예시 테케도 맞았고, 혹시나 하여 다른 사람들의 풀이랑 내 풀이도 비교해보았는데, 접근 방식이 동일하다.

그런데, 제출만하여 계속 틀렸다고만 뜨고, 제출 이력에는 표시조차 되어 있지 않다. 왜 틀렸는지는 알려줘야지....

거의 20번은 넘게 제출을 한 것 같은데.. 그래서 일단 개발자 톡에 문의를 넣어놓았고, 내 풀이상의 문제일 수 도 있을것 같아 코드도 함께 게시해 놓았다.

부분합 사용

이 문제는 부분합을 사용하면 아주 쉽고 간단하게 풀이할 수 있다.

부분합??

예를 들어서 5명의 학생이 있고, 각각의 점수는 20, 40, 10, 80, 30 이라고 하자.

그러면 크기가 5인 배열에 1명까지 더한 값, 2명까지 더한 값...이렇게 저장하는 것이다.

즉 arr이라는 크기가 5인 배열이 있으면

arr[0] =20

arr[1] = 20+40 = arr[0]+40

arr[2] = 20+40+10 = arr[1]+10

...

이렇게 이전에 저장해둔 값에 새로운 값을 추가로 저장해 총합을 구해 가는 것이다.

배열의 인덱스는 학번과도 같고(문제에서는 1부터 시작하지만, 예시로는 0부터 해도 무방), 만약 1번 학생부터 3번 학생까지의 점수 평균을 구한다면..

3번학생까지의 부분합-0번학생까지의 부분합 = 1번 학생부터 3번학생까지의 점수 합

이기 때문에, 구간이 주어지면 이미 구해진 합을 이용해 구간 합을 쉽게 구할 수 있다.

그리고 1번 학생부터 3번 학생까지 니까 (3-1+1)로 나누어 주면 평균은 바로 구할 수 있다.

따라서 아래와 같은 순서로 진행한다.

1. 학생 수인 N과 구간 수인 K를 먼저 받아서 저장한다.

2. 1부터 i번(1<=i<=N)까지의 학번을 갖는 학생 들의 점수 합을 저장하는 크기가 N+1인 벡터(또는 배열)를 생성한다 => 0번은 0으로 초기화 할 것이다.

3. 입력으로 학생들의 점수를 받을 때, 벡터에 합을 저장해준다.

4. 입력으로 K개의 구간 정보를 입력 받을 때, 앞에서 구한 부분합을 이용해서 평균을 바로 출력한다.

전체 코드는 아래와 같다.

#include<iostream>
#include<vector>

using namespace std;

int main(int argc, char** argv)
{
  int N,K;
  
  cin>>N>>K;

  vector<double> prefixSum(N+1);

  prefixSum[0]=0;
  
  for(int i=1; i<N+1; i++){
    int S;
    cin>>S;
    prefixSum[i] = prefixSum[i-1]+(double)S;
  }

  int A,B;
  for(int i=1; i<K+1; i++){
    cin>>A>>B;
    printf("%.2f\n", (double)(prefixSum[B]-prefixSum[A-1])/(double)(B-A+1));
  }

  return 0;
}

다른 사람들의 코드랑 비교해보아도, 이상이 없, 예제도 통과하는데, 틀린 이유를 모르겠으나.. 일단은 올려둔다.

예외를 발견한다면 알려주세요!!!