[백준 11659] 구간 합 구하기 4
구간 합의 개념을 그대로 적용해보는 문제입니다.
구간 합(Prefix Sum)이란 수들의 나열에서 특정 구간의 합을 의미합니다.
일반적으로 어떤 리스트 A가 존재할 때, A[i]부터 A[j]까지의 리스트 합을 구하는 문제인데
예를 들어, A = [5, 4, 3, 2, 1] 라고 가정하면
A[1]에서 A[3]까지의 합을 구하는 예시 문제가 이에 해당합니다.
이러한 문제를 해결할 때 합 배열을 따로 미리 구해놓지 않은 상태에서 직접 계산하려면
시간 복잡도가 커지는 어려움이 발생합니다.
따라서, 데이터를 입력받는 시점에 합 배열을 미리 만들어놓는 것이 유리합니다.
합 배열 S는
S[i] = A[0] + A[1] + A[2] + … + A[i - 1] + A[i], 즉 A[0]부터 A[i]까지의 합으로 정의합니다.
따라서 자연스럽게 i에서 j까지의 구간 합을 구할 때는 S[j] - S[i - 1]로 구할 수 있습니다.
A = [5, 4, 3, 2, 1] 라고 가정하면 S = [0] + [5, 9, 12, 14, 15]
(아무것도 더하지 않았을 때의 합은 0 이므로 맨 앞에 init prefix sum으로 0 을 붙여줍니다.)
i = 1, j = 3 이라고 가정했을 때, S[3] - S[0] = 12
=> (첫번째 수 5 + 두번째 수 4 + 세번째 수 3)
따라서, 위에서 설명한 개념들을 코드로 옮기면 다음과 같습니다.