백준 11659번 구간 합 구하기 4

< 백준 11659번 구간 합 구하기 4 - 마포 코딩박 >

사용한 알고리즘: Prefix Sum ( 구간합 배열 )


 구간합 배열을 구해 출력하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 8~12)
  'pSum[x] : 1~x 구간의 합' 이라고 설정하였습니다.
 입력을 받음과 동시에 구간합을 구합니다. 'pSum[x] = pSum[x-1]+x성분값' 입니다.

(2) (코드 13~18)
 s~e 성분합 = pSum[e] - pSum[s-1] 입니다. 이를 사용하여 M개의 입력으로 주어지는 i~j 구간합을 출력합니다.