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

 

문제 풀이 순서는 아래와 같다.

1. 데이터의 개수 N과 질의 개수 M 입력

2. 구간 합을 구할 대상 배열 입력

3. 구간 i,j 입력

4. 출력

 

이전 글에 구간 합에 대한 내용을 정리했으니

참고하길 바란다.

https://binaryroot.tistory.com/17

[자료구조] 구간 합

 

글을 확인했다면, 풀이를 시작해보자.

 

 

N과 M 입력

int n,m;
cin >> n >> m;

 

배열은 100000를 넘을 수 없으니

const로 미리 선언해주기

const int NMAX = 100020;

int arr[NMAX];

 

그리고 입력하기

처음부터 구간 합 공식에 넣고, 구간 합을 구해놓는다면

시간 복잡도는 줄어들 것이다.

for(int i = 1; i <= n; i++){
   cin >> arr[i];
   prefixSum[i] = prefixSum[i-1] + arr[i];
}

 

이제 구간 합을 구하여 계산해보자.

int a,b;
for(int i = 0; i < m; i++){
   cin >> a >> b;
   cout << prefixSum[b] - prefixSum[a-1] << '\n';
}

• 위에서 입력한 M개의 쿼리에 대해 a~b 구간의 합을 출력한다.
• prefixSum[b] - prefixSum[a-1]를 통하여 arr[a]부터 arr[b]까지의 합을 O(1)로 계산 가능하다.

 

 

 

전체 코드

#include <iostream>

//구간 합 구하기4
using namespace std;
typedef long long ll;

const int NMAX = 100020;

int arr[NMAX];
ll prefixSum[NMAX];

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

    int n,m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        prefixSum[i] = prefixSum[i-1] + arr[i];
    }

    int a,b;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        cout << prefixSum[b] - prefixSum[a-1] << '\n';
    }
}

 

실버3의 문제였다. 

구간 합에 대한 기본적인 지식이 없다면 풀 수 없는 문제이지 않을까 싶다.

해당 개념을 공부하지 않은 상태였다면 나는 과연 이 문제를 풀 수 있었을까?

아마.. 없었을 것 같다.

정확하게 알고 문제를 많이 풀어보자.

 

 

 

 

 

 

 

 

 

더 좋은 풀이가 있다면 댓글로 알려주세요 !!

피드백 환영입니다☺️