[BOJ] 백준 11659 구간 합 구하기 4 (Swift)

문제

11659번: 구간 합 구하기 4

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j

www.acmicpc.net

이 문제는 누적 합을 구해서 쉽게 풀이할 수 있습니다.

[5, 4, 3, 2, 1] 배열의 누적합을 구한다면
[5, 9, 12, 14, 15] 가 될 것입니다.

2 ~ 4번까지의 합은 4 + 3 + 2 로 9가 됩니다.

누적합 배열을 보시면 4번째 요소가 의미하는 것이 1 ~ 4까지의 합이고,
1번째 요소가 의미하는 것은 0 ~ 1까지의 합입니다.

4번째 요소 - 1번째 요소 = 1 ~ 4까지의 합 - 0 ~ 1까지의 합 = 즉, 2 ~ 4까지의 합을 구할 수 있습니다.

문제를 풀이할 때,
편의성을 위해 배열에 0번째에 0을 삽입시켜주어서 계산하였습니다.

누적 합 알고리즘의 기본적인 문제였습니다.