[백준/C++] 11659번 구간 합 구하기 4 (DP)

백준 11659번 구간 합 구하기 4

문제 1 변수 stack 초과

N, M, j, k 의 제한이 100,000이다. 

이 모든 변수들의 배열을 100,000으로 주면 STACK 초과가 뜬다.

처음은 아래 처럼 풀려고 했지만, 스택 초과 오류가 떴다. 배열 공간을 낮춰주니 정답은 맞았지만 바꿔줘야 했다. 

#include<iostream>
#include<vector>
using namespace std;
int d[100004];
int main() {

	int n,m;
	cin >> n>> m;
	vector<int> vec;
	int i[100004];
	int j[100004];
	int N[100004];
	for (int i = 1; i <= n; i++) cin >> N[i];
	for (int k = 1; k <= m; k++) cin >> i[k] >> j[k];

	for (int k = 1; k <= m; k++) {
		for (int p = i[k]; p <= j[k]; p++) {
			d[k] += N[p];
		}
		cout << d[k] << endl;
		//d[k] = N[i[k]]
	}
	
	//cout << d[n] << endl;
	return 0;
}

 

문제 2 시간 초과

시간 제한 1초가 중요한 문제이다.

먼저, d[i]의 값을 다 계산 및 저장해놓고 범위를 받아 출력하는 형식으로 바꿨다. 

그랬더니 확실히 시간복잡도가 줄었다. (다만 여기까지만 했을 때 시간초과가 떴다)

 

여기서 제일 중요한 점은 아래 코드 중 

ios::sync_with_stdio(0);
cin.tie(0);

이 코드를 추가해줘서 통과를 했다는 점이다. 

 

1. ios::sync_with_stdio(0);
   • C++의 iostream과 C의 stdio를 동기화하지 않겠다는 의미입니다.
   • 기본적으로 C++의 cin, cout 등은 C의 scanf, printf와 동기화되어 있습니다. 이를 비활성화하면 동기화 오버헤드가 제거되어 성능이 향상됩니다.
2. cin.tie(0);
   • cin과 cout의 묶음을 풀어줍니다.
   • 기본적으로 cin을 호출하기 전에 cout의 버퍼를 비우도록 되어 있습니다. 이로 인해 불필요한 플러시가 발생하여 성능이 저하될 수 있습니다. 이를 비활성화하면 성능이 향상됩니다.

이렇게 입출력의 제한을 풀어줌으로써 시간복잡도를 낮췄다.

시간 초과의 여러변수 중 하나임을 주의하자. 

#include<iostream>
#include<vector>
using namespace std;
int d[100004];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n>> m;
	//vector<int> vec;
	//int i[100004];
	//int j[100004];
	int N[100004];
	for (int i = 1; i <= n; i++) cin >> N[i];
	//for (int k = 1; k <= m; k++) cin >> i[k] >> j[k];
	
	d[0] = 0;
	d[1] = N[1];
	for (int i = 2; i <= n; i++) {
		d[i] = d[i - 1] + N[i];
	}

	for (int k = 0; k < m; k++) {
		int i, j;
		cin >> i >> j;
		cout << d[j] - d[i-1] << '\n';
	}
	return 0;
}