[C++] 백준 11659번: 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

• 풀이 방법

다이나믹 프로그래밍으로 풀 수 있는 문제입니다.

d[i] : i번째 수까지의 합

a[i] : i번째 수

따라서 i번째 수부터 j번째 수까지 합은 d[j] - d[i] + a[i] 이 됩니다.

 

입출력이 많기 때문에 cin.tie(0)을 해주어야 합니다.

 

cin.tie(0) : cin은 cout에 묶여있는데, 이는 cin을 할 때마다 cout의 버퍼를 먼저 비운다는 것을 의미합니다. 따라서 이 묶음을 풀어주면 빨라진다고 합니다. (여러 케이스에 대해 입력과 출력을 반복해야 할 때는 필수)

​

• 소스 코드

#include <bits/stdc++.h>
using namespace std;
int a[100001];
int d[100001];
int s, e;
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        d[i + 1] = d[i] + a[i];
    }

    for (int i = 0; i < m; i++)
    {
        cin >> s >> e;
        cout << d[e] - d[s] + a[s - 1] << '\n';
    }
    return 0;
}