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

#문제

#풀이

#include <iostream>

using namespace std;

int arr[100001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	arr[0] = 0;

	for (int i = 1; i <= n; ++i)
	{
		int x;
		cin >> x;
		arr[i] = arr[i - 1] + x;
	}

	while (m--)
	{
		int x, y;
		cin >> x >> y;

		long long total = arr[y] - arr[x - 1];

		cout << total << '\n';
	}

	return 0;
}

#정리

n개의 수를 받고, m개의 구간 사이 합을 출력하는 문제. 직관적으로 x-y구간을 받을 때 마다 각 배열을 더해서 출력하면 되겠다고 생각했지만, 시간초과가 나서 1트는 실패. 큰 값을 미리 계산하고 출력해야 했기에, DP를 사용해서 풀어야 겠다고 생각했다. 처음 단계에서 n개의 숫자를 받을 때, 미리 1부터 받은 숫자까지 합을 차례로 저장했다. 1부터 y까지의 구간의 합은 arr[1] + arr[2] + … + arr[y]이기 때문에 바로 출력하면 되고, x부터 y까지의 구간의 합은 arr[y] - arr[x - 1]을 출력하면 답이 나왔기 때문에 수식을 적용해서 해결했다.

#문제

#풀이

#정리

Enjoy Reading This Article?