풀이법
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
'Coding_Test_C++' 카테고리의 다른 글
BaekJoon 1926번: 그림 (0) | 2021.04.26 |
---|---|
BaekJoon 2193번: 이친수 (0) | 2021.04.21 |
BaekJoon 1912번: 연속합 (0) | 2021.04.18 |
BaekJoon 11726번: 2xn 타일링 (0) | 2021.04.17 |
BaekJoon 1149번: RGB거리 (0) | 2021.04.16 |