💎 문제
수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
💎 입력
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
💎 출력
총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.
💎 제한
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 100,000
- 1 ≤ i ≤ j ≤ N
💎 풀이 방법
이번 글은 좀 짧을텐데 문제는 우선 굉장히 쉬웠으나 for문을 풀기 전에 주의할 점을 짚고 가야할 점을 확인할 수 있어서 좋은 문제였다. 누적 합을 이용해서 큰 크기의 공간을 이중 for문을 사용할 경우 시간복잡도가 O(n^2) 형태로 안좋은 효율을 보여줄 수 있기 때문에 vector을 이용하여 그 인덱스까지의 범위에 해당하는 누적된 합의 값을 넣어주었다.
for(int i = 1;i <= N;i++){
int temp;
cin >> temp;
result += temp;
v[i] = result;
}위와 같은 방식을 이용하여 누적된 합이 vector의 인덱스에 저장될 것이며 특정한 구간을 구하고자 한다면 시작하는 범위 이전 까지 더해진 누적 합과 끝 범위에 해당하는 누적 합의 차이를 구해주면 된다.
이 때! 가장 중요한 이 문제의 핵심은 for문을 이용할 때에 입출력이 for문 안에 들어가게 되면 시간초과가 발생할 수 있다는 점이다. 따라서 그에 해당하는 처리를 해주어야 하는데 나의 경우는 c++를 사용하여 주로 알고리즘 문제를 풀기 때문에
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);위와 같은 처리를 해주었다. for문을 풀 때에는 이 점을 항상 염두해서 크기가 큰 반복문을 돌릴 때 입출력이 들어간다면 시간 초과가 발생할 수 있다는 것을 생각하자!!!!
위의 내용은 이 링크를 참고하자! https://www.acmicpc.net/problem/15552
💎 전체 코드
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
vector <int> v(100001);
int N, M;
int main(int argc, const char * argv[]) {
int result = 0;
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
v[0] = 0;
for(int i = 1;i <= N;i++){
int temp;
cin >> temp;
result += temp;
v[i] = result;
}
for(int i = 0;i < M;i++){
int a, b;
cin >> a >> b;
cout << v[b] - v[a - 1];
cout << "\n";
}
return 0;
}💎 고민
진짜 10분도 안걸려서 푼 것같은데 중요한 점을 알아갈 수 있었다. 두 가지가 있는데 첫 째는 반복문의 시간복잡도를 항상 고려할 것. 크기가 큰 반복문을 돌리게 될 때 이중 반복문을 사용하면 최악의 경우 제곱배로 늘어나기 때문에 안좋은 효율을 보일 수 있기 때문에 이중 반복문은 크기가 작을 때만 사용하도록 하자. 두번 째는 크기가 큰 반복문 안에 입출력문이 들어가는 것을 고려하자. 앞서 풀이와 같이 다 잘 풀어놓고 시간초과로 틀리지 말도록,,, 꼭 기억해두자!!!
화이팅!!!
