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

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

11659번: 구간 합 구하기 4

그냥 쉽게 생각해서 2중 for문 사용했는데 역시나 시간초과로 틀림 ㅎㅎ;;

 

<시간초과 된 코드> 틀리는게 당연함 입력값 최대가 N, M 둘다 100,000임

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

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

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

	vector<int> v;

	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		v.push_back(x);
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		long long int sum = 0;

		for (int i = a-1; i < b; i++) {
			sum = sum + v[i];
		}

		cout << sum << '\n';
	}
}

<맞는 답>

dp를 사용해서 풀면 시간초과 되지 않고 풀린다.

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

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

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

	int* arr = new int[n];

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

	int* sum = new int[n + 1];

	sum[0] = 0;
	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + arr[i - 1];
	}
	
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		int ans = sum[b] - sum[a - 1];
		cout << ans << '\n';
	}
	
}

이중 for문을 사용해서 풀지 않는게 핵심인 것 같다. 또한

ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

이것들도 잊지않고 넣어주기!