BaekJoon 11659번: 구간 합 구하기 4

풀이법

arr 배열이 100,000까지 있기에 시간 초과를 방지하기 위해서는 DP를 사용해야 한다.

입력과 동시에 모든 배열의 합을 구해서 합의 배열을 만들어두고

arr[j] - arr[i-1]을 이용하면 쉽게 풀 수 있는 문제이다.

#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;

int n, m;
int arr[100001];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	arr[0] = 0;
	int temp = 0;
	for (int i = 1; i <= n; i++)
	{
		int a;
		cin >> a;
		temp += a;
		arr[i] = temp;
	}
	vector<int> ans;
	for (int k = 1; k <= m; k++)
	{
		int i, j;
		cin >> i >> j;
		ans.push_back(arr[j] - arr[i - 1]);
	}
	for (int i = 0; i < ans.size(); i++)
	{
		cout << ans[i] << "\n";
	}
}

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest