https://www.acmicpc.net/problem/11659
문제
> 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
> 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다.
둘째 줄에는 N개의 수가 주어진다.
수는 1,000보다 작거나 같은 자연수이다.
셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
> 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.접근
구간합 구하는 문제는 누적합을 사용한다.
누적합을 구하기 위한 전체 수열, 배열을 입력받으면서 동시에 현재 입력받은 곧까지의 합도 같이 구한다.
입력이 끝나면 이를 기반으로 구간합을 구할 때 구간이 주어지면 합에 구간을 인덱스로 넣어 뽑아내면 된다.
문제해결
> 전체 구간 N과 구할 구간 합의 수 M을 입력받는다.
> 구간이 1부터 시작하므로 N의 수열과 sum 누적합 배열의 크기를 N+1로 선언해주고 입력받으면서
i번째 까지의 합은 직전 번의 합+ i번의 현재 값을 더해주고 0번인덱스의 값을 빼준다.
> M번의 while문으로 구간을 입력받고 b구간에서 a-1구간을 빼주면 a부터 b까지의 합이 나온다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> num(N + 1, 0);
vector<int> sum(N + 1, 0);
for (int i = 1; i <= N; i++)
{
cin >> num[i];
sum[i] = sum[i - 1] + num[i] - sum[0];
}
while (M--)
{
int a, b;
cin >> a >> b;
cout << sum[b] - sum[a - 1] << '\n';
}
}
후기
이차원배열 형태의 누적합은 해봤지만 일차원은 안해봐서 했다. 이차원과 다르게 굳이 0번째를 빼줄 필요가 없어보인다. 어느 부분에서 누적합을 구하면서 가야할지 버벅거렸다. 어렵지 않은 문제였는데 기본을 다시 다지자.
