[C++/Baekjoon] 11659번: 구간 합 구하기 4 //C++ 시간초과 해결

문제

---

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

출력

---

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

풀이

---

초기 코드 (시간 초과)

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

int main() {
  
  int N, M;
	cin >> N >> M;
	vector<long>arr(N+1);
	arr[0] = 0;


	for (int i = 0; i < N; i++)
		cin >> arr[i];

	
	for (int i = 0; i < M; i++) {
		int a, b;
		int cnt = 0;
		cin >> a >> b;
	
		for (int j = a; j <= b; j++) {
			cnt += arr[j - 1];
		}
		cout << cnt << "\n";
	}

	return 0;
}

시간초과 당한 초기 코드이다.

보면 알겠지만... 반복문이 너무 많다.

사실 처음에는 동적할당을 new로 해주었는데 다들 vector를 쓰시기에 바꿔 봤다.

 

* vector<int>와 new int 차이점

: vector는 동적으로 확장/축소가 자유로운데 new는 초기에 동적할당을 받으면 그 뒤로 더 늘려지지 않는다.

 

 

수정 코드(시간 초과)

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	
	vector<int> arr(n+1);
	for (int i = 1; i <= n; i++) {
		int num;
		cin >> num;	
		arr[i] = arr[i - 1] + num;
	}

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

	return 0;
}

반복문을 줄이기 위해 누적 합을 저장하는 코드로 바꾸었다.

처음부터 이전 인덱스에 입력 값을 더하는 방식으로 누적 합을 배열에 저장한다면

불필요한 반복문을 줄일 수 있다.

 

근데... 이상하게도 자꾸 시간초과가 된다.

 찾아 보니까, 입출력으로 인해 시간초과가 되는 거라고 한다.

 

 

C++ 시간초과 해결방법

참고 https://ip99202.github.io/posts/%EC%9E%85%EC%B6%9C%EB%A0%A5-%EC%86%8D%EB%8F%84-%EC%A4%84%EC%9D%B4%EA%B8%B0/

 

 

1. ios::sync_with_stdio(false);

해당 코드를 추가하면, c와 c++ 표준 stream의 동기화를 비활성화한다.

즉, 기존에 c의 printf, scanf와 c++의 cin, cout을 혼합하여 사용할 수 있게 해 준 동기화를 해제함으로써

동기화 과정에서 필요로 하던 시간이 절약되어 입출력 속도가 빨라진다고 한다.

(C++ stream들이 독립적인 buffer를 갖게 되어 buffer의 수가 줄어들어서 빨라지는 거라고 한다.)

 

2. cin.tie(null); cout.tie(null);

원래는 cout과 cin은 묶여 있다.

즉, 입력 전에 출력이 있었을 경우에 buffer를 flush한 뒤에 출력한다. 

그럼 입출력 반복시에 buffer를 지우는 과정에서 시간이 소모된다.

이 묶임을 푸는 게 위 코드이다.

입출력 순서를 보장받을 순 없지만, 시간은 절약이 된다고 한다.

 

 

 

최종 코드

#include <iostream>
#include <vector>

using namespace std;

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

	int n, m;
	cin >> n >> m;
	
	vector<int> arr(n+1);
	for (int i = 1; i <= n; i++) {
		int num;	
		cin >> num;	
		arr[i] = arr[i - 1] + num;
	}

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

	return 0;
}

드디어 보는 초록 글씨