11659번 (Silver 3)

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

구간합 알고리즘을 사용하여 해결하는 간단한 문제이다.

 

#include <iostream>
#include <vector>

int main() {

	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	int N, query, start, end;


	std::cin >> N >> query;

	int arr_sum[100001] = {};


	for (int i = 1; i <= N; ++i) {
		int temp;
		std::cin >> temp;
		arr_sum[i] = arr_sum[i - 1] + temp;

	}

	for (int i = 0; i < query; ++i) {
		std::cin >> start >> end;
		//int sum = arr_sum[end] - arr_sum[start - 1];
		std::cout << arr_sum[end] - arr_sum[start - 1] << "\n";
	}

	return 0;
}

처음에는 vector를 사용해서 풀었으나, 시간초과가 발생하였다.

vector는 동적할당 문제때문에 그런듯 하다.

문제에서 100000이하의 자연수라고 주어졌기 때문에 그냥 크기가 100001인 배열자체를 선언하고 사용하였다.

 std::ios_sync_with_stdio(false); std::cin.tie(NULL);, std::cout.tie(NULL);을 사용해서 시간을 줄이고, std::endl;사용대신 "\n"을 사용해서 flush가 발생하는 일을 없애고 다시 수행하니 성공!