[PS] 백준 #17390. 이건 꼭 풀어야 해!

문제 정보

• 난이도: 실버 III
• 문제 주소: https://www.acmicpc.net/problem/17390
• 이 문제를 푼 이유: 그룹 연습 Div 2

문제

숭실골 높은 언덕 깊은 골짜기에 출제로 고통 받는 욱제가 살고 있다!

욱제는 또 출제를 해야 해서 단단히 화가 났다. 그래서 욱제는 길이 N짜리 수열 A를 만들고, A를 비내림차순으로 정렬해서 수열 B를 만들어 버렸다!! 여기서 B를 출력하기만 하면 문제가 너무 쉬우니까 하나만 더 하자. 아래와 같은 질문이 무려 Q개나 주어진다!! (ㅎㅎ;; ㅈㅅ.. ㅋㅋ!!)

• L R:  BL + BL+1 + ... + BR-1 + BR 을 출력한다.

Figure 1. 모든 참가자가 문제를 풀 수 있을 것이라고 기대하는 욱제의 표정

욱제의 질문에 답하고 함께 엠티를 떠나자!!

 

나의 풀이

오랜만에 문제를 풀어서 문법적으로 헷갈리는 내용이 많았다. 이 문제의 답은 최대 30만 * 1000 == 30억까지라서 int 자료형 대신 long 자료형을 써야겠다는 생각을 먼저 했다. 그리고 BL + BL+1 + ... + BR-1 + BR 을 보자마자 누적합끼리 빼서 구하면 되겠다 해서 [A 입력 -> psum 계산 -> 각 l, r마다 psum끼리 빼서 구하기] 형태로 코드를 짰다. 

처음에 시간초과가 떠서 뭐가 문제일지 한참 고민했다. 과거에 벡터의 push_back이 emplace_back보다 느리다는 얘기가 생각나서 emplace_back으로도 변경해봤지만, 계속 시간초과가 떴다. 곰곰히 생각해보다가 갑자기 저번 그룹 대회때 그룹장님이 내 코드에서 cin.tie, cout.tie 를 써서 속도가 빨라졌다는 얘기가 생각났다. 이 코드를 추가하니까 바로 시간 초과가 해결되서 통과되었다.

#include <bits/stdc++.h>
using namespace std;

// 시간 초과 1: psum 벡터를 emplace back으로 변경
// 시간 초과 2: cin.tie cout.tie 추가

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

	int n, q;
	cin >> n >> q;
	vector<int> A;
	vector<long> psum;

	// A입력
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		A.push_back(a);
	}

	// A 비내림차순 정렬 
	sort(A.begin(), A.end());
	psum.emplace_back(A[0]);

	// psum 계산
	for (int i = 1; i < n; i++) {
		psum.emplace_back(psum[i - 1] + A[i]);
	}

	// 각 l, r마다 psum 빼서 구하기
	for (int i = 0; i < q; i++) {
		int l, r;
		cin >> l >> r;
		if (l == 1) cout << psum[r - 1] << "\n";
		else cout << psum[r-1] - psum[l-2] << "\n";
	}
}