[백준/C++] 17390 이건 꼭 풀어야 해!

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

17390번: 이건 꼭 풀어야 해!

코드

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

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

int main()
{
    FASTIO;
	int n, q;
	cin >> n >> q;
	vector<int> v(n);
	vector<int> sum(n+1);
	for (int i = 0; i < n; i++) cin >> v[i];
	sort(v.begin(), v.end());

	sum[1] = v[0];
	for (int i = 2; i <= n; i++) sum[i] = sum[i - 1] + v[i-1];

	while (q--)
	{
		int a, b;
		cin >> a >> b;
		cout << sum[b] - sum[a - 1] << "\n";
	}
	return 0;
}

코드 설명

먼저 수열의 길이 N과 질문의 개수 Q를 입력받는다. 이후 N개의 정수를 입력받는데, 이를 벡터에 저장한다. 이후 벡터를 오름차순(비내림차순)으로 정렬해준다. 

 

이후 누적합을 구해준다. 이전까지의 수열 원소의 합 + 현재 원소의 합을 sum[i]에 저장하면 된다. 이후 질문의 개수대로 시작과 끝을 입력받는다. 시작 위치 a~끝 위치 b까지의 합은 처음~b까지의 합에서 처음~a-1까지의 합을 빼주면 된다.

 

 

느낀 점

N개의 정수를 입력받고 나서 오름차순으로 정렬해준 뒤에 누적합 원리를 써서 풀면 되는 문제다. 바로 흐름 잡고 풀었는데도 시간초과가 나서 당황했는데, 알고보니 빠른 입출력을 적용하지 않았었다.

바로 main함수 시작부에 FASTIO; 적어주고 다시 제출하니 통과했다.