백준 11659 구간합구하기4 c언어

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

나의 첫번쨰 접근코드)

#include <stdio.h>

int main()
{
    int N,M,i,j,result;
    int first[100000] = {0};
    int last[100000] = {0};
    int arr[100000] = {0};

    scanf("%d %d", &N, &M);
    i = 0;
    while (i < N)
    {
        scanf("%d", &arr[i]);
        i++;
    }
    i = 0;
    while (i < M)
    {
        scanf("%d %d", &first[i], &last[i]);
        i++;
    }
    i = 0;
    while (i < M)
    {
        j = first[i] - 1;
        result = 0;
        while (j <= last[i] - 1)
        {
            result += arr[j];
            j++;  
        }
        if (result == 0)
            printf("%d\n", arr[j]);
        else
            printf("%d\n", result);
        i++;
    }
    return (0);
}

                                   |

                                   |

                                   |

                                  V

고친 나의코드)

#include <stdio.h>

int arr[100001];
int sum[100001];
 
int main() 
{
    int N, M, i, j;
    int	arr[100001];
    int	sum[100001];
    int result;
    scanf("%d %d", &N, &M);
 
    i = 1;
    while (i <= N) 
    {
        scanf("%d", &arr[i]);
        sum[i] = sum[i - 1] + arr[i];
        i++;
    }
 	i = 0;
    while (i < M) 
    {
        scanf("%d %d", &i, &j);
        result = sum[j] - sum[i - 1];
        printf("%d\n", result);
        i++;
    }
    return (0);
}

시간초과가 발생했을떄 while문이 두번이라서 발생한것인가 의문을 품었지만 연산과정에서 시간 초과가 발생했을것이라 생각했다.

따라서 연산과정을 짧게 할 수있는 방법이 무엇인가 생각해보았다

주어진 범위 i 에서 j까지의 숫자합  == j 까지의 모든 숫자합 - i 까지의 모든 숫자합 

위의 방법을 사용하면 간단히 연산될것이라 생각했다.

 

포인트)

각각의 누적합을 구하는 방법을 위에 sum각각의 인덱스에 넣는 방법을 잘 알아두면 적절할때  잘 쓰일거 같다.