개요

백준 11441: 합 구하기

• 입력
  첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 각 구간을 나타내는 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)

• 출력
  총 M개의 줄에 걸쳐 입력으로 주어진 구간의 합을 출력한다.

접근 방식

1. N이 10만이고, M이 10만이므로 M개의 횟수마다 N개의 합을 다루려면
   최대 100억개의 연산을 해야하므로 시간초과가 난다.

2. 따라서 입력값 받는단계에서 미리 i-1값까지 더한 합배열Sum[i]을 계산하여 저장해갔다.

for (int i = 1; i <= N; i++) {
		cin >> inputArr[i];
		//i까지의 합은 i-1까지의 합 + i번째 원소
		Sum[i + 1] = Sum[i] + inputArr[i];
	}

3. 따라서 i번째부터 j번째까지의 합은

Sum[tmp2 + 1] - Sum[tmp1]

으로 표현하면 된다.

전체 코드

#include<iostream>

using namespace std;
int N = 0, M = 0,tmp1=0,tmp2=0;
int inputArr[100'001];
//index-1까지 더한 합배열
int Sum[100'001];

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> inputArr[i];
		//i까지의 합은 i-1까지의 합 + i번째 원소
		Sum[i + 1] = Sum[i] + inputArr[i];
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> tmp1 >> tmp2;
		cout<<Sum[tmp2 + 1] - Sum[tmp1]<<'\n';
	}
}



int main() {
	//입출력 관련해서 시간 감소
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	Input();

}