
코드 - 시간초과
// 시간초과
#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;
}
'C++ > 백준 C++' 카테고리의 다른 글
[C/C++] 백준 1149번 RGB거리 - 참고 (2) | 2023.11.25 |
---|---|
[C/C++] 백준 9095번 1, 2, 3 더하기 - 참고 (1) | 2023.11.24 |
[C/C++] 백준 1182번 부분수열의 합 - 참고 (2) | 2023.11.23 |
[C/C++] 백준 1269번 대칭 차집합 (2) | 2023.11.22 |
[C/C++] 백준 30700번 KOREA 문자열 만들기 (2) | 2023.11.22 |