[JAVA] 성적 평균

https://softeer.ai/practice/6294

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

언어시간메모리

 

JavaScript	2초	256MB
C	1초	256MB
C++	1초	256MB
Java	2초	256MB
Python	2초	256MB
C#	2초	256MB
Kotlin	2초	256MB
Go	2초	256MB
Swift	2초	256MB

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

 

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

제약조건

1 ≤ N ≤ 106 인 정수

1 ≤ K ≤ 104 인 정수

1 ≤ Si ≤ 100 인 정수

1 ≤ Ai ≤ Bi ≤ N

입력형식

첫 번째 줄에 학생 수 N과 구간 수 K가 주어진다.

두 번째 줄에는 학생의 성적 Si (1 ≤ i ≤ N)가 주어진다. i + 2 (1 ≤ i ≤ K)번째 줄에는 i번째 구간 Ai, Bi가 주어진다.

출력형식

i번째 줄에 i번째 구간의 성적평균(소수셋째자리에서 반올림)을 출력한다.

차이가 0.01이하이면 정답으로 채점됨.

입력예제1

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

출력예제1

26.67 45.00 50.00

---

 

처음에는 DP 문제라 생각이 들어 DP로 접근을 했었다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {

      Scanner s = new Scanner(System.in);
      
      int N = s.nextInt(); // 학생 수
      int K = s.nextInt(); // 구간 수

      double[] scores = new double[N];
      double[][] dp = new double[N][N];
      
      for(int i=0; i<N; i++) {
        scores[i] = s.nextInt();

		// dp로 해결 : j~i까지의 합 저장
        dp[i][i] = scores[i];
        for(int j=i-1; j>=0; j--) {
         dp[j][i] = dp[j][i-1] + scores[i];
        }
      }


      
      
      double[] answer = new double[K];

      for(int n=0; n<K; n++) {
        int i = s.nextInt();
        int j = s.nextInt();

        answer[n] = dp[i-1][j-1] / (j-i+1);
      }

      for(int i=0; i<K; i++) {
        System.out.println(String.format("%.2f", answer[i]));
      }
    }
}

 

그런데 이렇게 푸니 오답이 나왔다.

이유를 살펴보니 메모리 초과 문제였다. 결국 DP가 아니라 베이직하게 푸는 문제였던 것이다.

 

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {

      Scanner s = new Scanner(System.in);
      
      int N = s.nextInt(); // 학생 수
      int K = s.nextInt(); // 구간 수

      double[] scores = new double[N];
      
      for(int i=0; i<N; i++) {
        scores[i] = s.nextInt();
      }


      
      
      double[] answer = new double[K];

      for(int n=0; n<K; n++) {
        int i = s.nextInt();
        int j = s.nextInt();

        double sum = 0;
        for(int k=i-1; k<=j-1; k++) {
          sum += scores[k];
        }
        sum /= (j-i+1);

        answer[n] = sum;
      }

      for(int i=0; i<K; i++) {
        System.out.println(String.format("%.2f", answer[i]));
      }
    }
}