백준 11659: 구간합 구하기 4

 

📃 문제: 백준 11659(구간합 구하기 4)

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

11659번: 구간 합 구하기 4

 

🥈 난이도: 실버 3

 

😲 사용한 개념: 구간합

S[i] = S[i-1] + A[i]

 

구간합 배열을 미리 구해놓으면, 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(n) -> O(1)로 감소한다.

 

 

 

📖 풀이 사고 과정

 

 

 

👩‍💻 구현 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int main(void) {
    int arr[100000], N, M, start, end, S[100000] = { 0, }, result[100000];
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        scanf("%d", arr[i]);
        //구간합 구하기
        if (i == 0) S[i] = arr[i];
        else S[i] = S[i - 1] + arr[i];

    }
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &start, &end);
        if (start != 0) result[i] = S[end] - S[start - 1];
        else result[i] = S[end];
    }
    for (int i = 0; i < M; i++) {
        printf("%d\n", result[i]);
    }
    return 0;
}