https://www.acmicpc.net/problem/11659
문제 풀이
누적합 배열을 생성해서 구간 합 문제를 해결했다.
처음 제출했을 때 시간복잡도가 O(N)이였는데도 시간초과가 나와서 당황했다.
ios::sync_with_stdio(false);
cin.tie(nullptr);
코드를 작성해서 main안에 넣어주니 시간 초과 문제가 해결되었다.
위의 코드들에 대해서는 다음번에 자세히 설명해 볼 예정이다.
소스 코드
#include <iostream>
using namespace std;
int sum[100001] = { 0 };
int num[100001] = { 0 };
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
for (int i = 1; i <= N; i++) {
cin >> num[i];
}
for (int j = 1; j <= N; j++) {
sum[j] = sum[j - 1] + num[j];
}
for (int t = 0; t < M; t++) {
int a, b;
cin >> a >> b;
cout << sum[b] - sum[a - 1] << '\n';
}
}
'알고리즘' 카테고리의 다른 글
[백준] 7562번 나이트의 이동 C++ 문제풀이 (0) | 2023.09.06 |
---|---|
[백준] 2630번 색종이 만들기 C++ 문제풀이 (0) | 2023.09.04 |
[백준] 1003번 피보나치 함수 C++ 문제풀이 (0) | 2023.09.01 |
[백준] 2606번 바이러스 C++ 문제풀이 (0) | 2023.08.31 |
[백준] 1012번 유기농 배추 C++ 문제풀이 (0) | 2023.08.30 |