softeer 문제

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

Code C 2023. 3. 26. 16:30

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

 

Softeer

연습문제를 담을 Set을 선택해주세요. 취소 확인

softeer.ai

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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));
    }
}
 
 cs

문제풀이 :

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

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]로 구할 수있다.