백준 11659 - 구간 합 구하기 4

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

알고리즘보다는 수학 기초 이론에 관련된 문제

 

매 입력마다 정직하게 반복문으로 합을 구하면 당연히 시간초과가 발생한다.

 

그래서 위 문제에서는 수열 An을 입력받은 뒤, A1부터 An까지의 합 Sn에 대하여

급수(수열의 합)의 성질 2가지를 활용해 답을 구했다.

 

1) S(n+1) = Sn + A(n+1)

 

2) Ai부터 Aj까지의 부분합 Ai+A(i+1)+...+A(j-1)+Aj 를 interval(i,j)라고 할때,

interval(i,j) = Sj - S(i-1)

 

ex) S5 - S(3-1) = A1+A2+A3+A4+A5 - (A1 + A2) = A3+A4+A5 = interval(i,j)

 

구현한 코드는 다음과 같다.

int main() {

...
    //sum[i] = Si = S(i-1) + Ai
    
    for (int i = 1; i < sum.size(); i++)
        sum[i] = sum[i - 1] + v[i - 1];
}


//interval(i,j) = Sj - S(i-1)
int getInterval(const vector<int>& sum, int start, int end) {
    return sum[end] - sum[start - 1];
}