구간 합 구하기 4( BOJ 11659 )

(1) 문제

11659. 구간 합 구하기 4 : https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

(2) 문제 이해하기

 

(3) 문제 해결하기

 

(4) 소스코드

#include <stdio.h>
#include <vector>
#define NMAX 100010
using namespace std;
 
// 입력 변수
int n, m, p, q;
int inp[NMAX];
 
// 누적합 변수
vector< int > sum;
 
// 결과 변수
vector< int > ans;
 
int main() {
    // 입력
    scanf("%d %d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d", &inp[i]);
 
    // 누적합 구하기
    sum.push_back(0);
    for(int i=1;i<=n;i++) sum.push_back(sum.back() + inp[i]);
 
    // 쿼리 처리하기
    for(int i=1;i<=m;i++) {
        scanf("%d %d", &p, &q);
 
        ans.push_back(sum[q] - sum[p] + inp[p]);
    }
 
    // 결과 출력하기
    for(int val:ans) printf("%d\n", val);
}

 

(5) 후기

누적합의 개념을 알 수 있는 문제라고 생각합니다. 배열을 배운 학생들에게 추천하는 문제입니다.