Softeer[level3] 성적평균 (C언어)

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

Softeer

Code:

#include <stdio.h>
 
int main()
{
    int n,k;
    scanf("%d %d", &n, &k);
    int arr[1000001] = { 0, };
    int dp[1000001] = { 0, };
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
        dp[i] = arr[i] + dp[i - 1];
    }
    int a, b;
    double sum = 0;
    while (k--)
    {
        scanf("%d %d", &a, &b);
        sum = dp[b] - dp[a - 1];
        printf("%.2lf\n", sum / (b - a + 1));
    }
}
 

문제풀이 :

구간을 구하는 문제이다. 다이나믹 방식으로 문제를 풀어야지 시간초과가 발생하지 않는다.

ex) 10 50 20 70 100이라고 하면

arr배열에는 {10 50 20 70 100}

dp배열에는 {10 60 80 150 250}이렇게 저장된다.

만약 구간 2에서 4까지의 합을 구하고 싶다면,

50 + 20 + 70 =140이 나와야 한다. 이 값은 dp에서 dp[4]-dp[1]로 구할 수있다.