C++/백준 C++

[C/C++] 백준 11659번 구간 합 구하기 4 - 참고

CE : 하랑 2023. 11. 23. 21:57

 

 

 

코드 - 시간초과

// 시간초과
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> num;
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;

		num.push_back(n);
	}

	for (int i = 0; i < M; i++) {
		int a, b;
		int sum = 0;
		cin >> a >> b;

		if (a != b) {
			for (int j = a; j <= b; j++) {
				sum = sum + num[j - 1];
			}

			cout << sum;
		}
		else if (a == b) {
			sum = num[a - 1];

			cout << sum;
		}

		cout << "\n";
	}

	return 0;
}

 

 

 

코드 - 정답

 

#include <iostream>
#include <vector>

using namespace std;
// 슬라이딩 윈도우 알고리즘
int main()
{
	cin.tie(0); // 코드를 작성하면 입출력 속도가 빨라진다. -> C와 C++ 표준 stream의 동기화를 비활성화
	cout.tie(0); // C++의 입출력인 cin, cout만 사용하도록 주의해야합니다.

	int N, M; 

	cin >> N>>M;

	vector<long> num(N + 1);

	for (int i = 1; i <= N; i++) { // n개의 수 -> 이전배열을 계속 더해주어 누적합을 시켜준다.
		long n;
		cin >> n;

		num[i] = num[i - 1] + n;
	}

	for (int i = 0; i < M; i++) { //  m개의 구간
		int a, b;
		cin >> a >> b;

		cout <<num[b]-num[a-1]<< "\n"; //  num[b] - num[a-1]을 출력하면 a부터 b까지의 누적합을 O(1)의 시간으로 구할 수 있다.
	}

	return 0;
}