백준 11659번 구간 합 구하기 4 문제 풀이

문제 설명

• 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

문제를 보고 든 생각

• 투 포인터
• 구간이 주어질 때 마다 계산을 하면 비효율적일 것 같다.
• arrSum 벡터에 0부터 i번째까지 합을 모두 저장하자. 그러면 arrSum[j] - arr[i] 는 구간합이 될 것이다.

풀이 간단 설명

1. 0번째 부터 i 번째 까지 합을 저장하는 vector<unsigned long long> arrSum
2. i부터 j까지 구간 합을 구하려면 arrSum[j] - arrSum[i-1]을 출력하면 된다.

코드

#include <iostream>
#include <vector>

using namespace std;

typedef unsigned long long ull;

vector<ull> arrSum;
int M;

void getInput(){
  int N; cin >> N;
  cin >> M;
  ull sumCnt = 0;
  arrSum.push_back(0);
  for(int i=0; i<N; ++i){
    int temp; cin >> temp;
    sumCnt += temp;
    arrSum.push_back(sumCnt);
  }
}

ull calSum(){
  int lp, rp; cin >> lp >> rp;
  --lp;
  
  return arrSum[rp] - arrSum[lp];
}

void solve(){
  getInput();
  for(int i=0; i<M; ++i){
    cout << calSum() << "\n";
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();

  return 0;
}

후기

• 투 포인터 문제를 풀면 항상 더 좋은 풀이가 있을 것 같다.