accumulate() 함수의 overflow 문제 해결 방법

알고리즘 문제를 풀 때, 많은 사람들이 accumulate()함수를 자주 사용할 것으로 생각합니다.

하지만, 해당 함수를 사용할 때 overflow에 대한 문제가 발생하여 for문으로 직접 합을 구하는 경우도 있을 것입니다.

 

accumulate()함수의 선언을 확인해보면 문제를 해결할 수 있습니다.

template <class _InputIterator, class _Tp>
_Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init);

[실제 accumlate() 함수의 선언은 이렇지 않습니다. 보기 편하도록 필요 없는 부분은 제거 하였습니다.]

 

여기서 중요하게 보아야 하는 것은 _Tp의 타입이 세번째 인수에 의해 결정 된다는 것입니다.

그러므로, 세번째 인수의 타입을 기존 타입보다 더 넓은 범위를 표현 할 수 있는 타입으로 한다면 overflow문제를 해결 될 것입니다.

 

예시)

int main() {
    vector<int> arr{numeric_limits<int>::max(),2};
    
    //overflow 발생
    long result1 = accumulate(arr.begin(), arr.end(), (int)0);
    //overflow가 발생하지 않음
    long result2 = accumulate(arr.begin(), arr.end(), (long)0);
    
    cout << "result1 : " << result1 << endl; // 출력 결과 : -2147483647
    cout << "result2 : " << result2 << endl; // 출력 결과 : 2147483649
    
    return 0;
}