11659: 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

설명

문제는 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 

• 1 <= N <= 1000

 

핵심 아이디어

제한이 있기 때문에 2중 for loop로 풀면 시간초과 날 수 있어서 누적 합(prefix sum)으로 으로 접근하기. 만약 누적 합을 사용하지 않고 구현하게 된다면 M,N의 입력 범위가 100,000이 넘어간다면 시간 복잡도는 O(NM)이 되므로 1초내에 구현할 수 없다.

• 누적 합(prefix sum) 알고리즘을 통해 구간 합을 빠르게 구할 수 있다.
• 각각의 합들을 새로운 배열에 저장해 뒀다가 나중에 입력에 구간이 들어오면 해당 구간을 index로 바꿔서 출력해주면 된다.
• 이때, index를 헷갈리지 않게 하지 위해 새로운 배열에 0을 추가해 둔다. 
• 매 입력이 들어올 때 P[right] - P[left-1]을 수행하면 계산 시간은 O(1)이 되고, 결과적으로 M개의 데이터와 N개의 입력이 있을 때, 전체 구간 합을 O(M+N)의 시간이 보장된다.

코드 구현

import sys
input = sys.stdin.readline

# 수의 개수 N, 합을 구하는 횟수 M
n, m = map(int, input().split())
# n개의 수가 주어진다.
data = list(map(int, input().split()))
# init prefix_sum
prefix_sum = [0]

temp = 0
for i in data: # 각각의 합을 배열에 누적해서 저장
	temp += i
	prefix_sum.append(temp)
# print(prefix_sum): [0, 5, 9, 12, 14, 15]
for i in range(m):
	a, b = map(int, input().split())
	print(prefix_sum[b] - prefix_sum[a-1])

C++

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

int n, m;
int arr[100001] = {0,};


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;

	// 배열 입력 받기
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	// 배열을 누적합으로 변경
	for (int i = 1; i <= n; i++) {
		arr[i] += arr[i - 1];
	}

	// 구간 입력 받고 누적합 출력
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;

		cout << (arr[b] - arr[a - 1]) << "\n";
	}


}