개요

백준 11659: 구간 합 구하기 4

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

• 출력
  총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

접근 방식

1. 수의범위가 너무 커서(10만) 그냥 단순히 접근하면
   N만큼 반복문 돌리고 각 반복문마다 M만큼 반복문을 돌려야해서
   시간이 O(N*M) 정도가 나온다.
   최대치가 10만,10만이라 100억으로 시간초과가 나온다.

2. 따라서 숫자를 입력받을때마다 바로바로 해당 숫자까지의 합을 저장하는
   합배열을 따로 만들어서 계산했다.

코드

#include<iostream>

using namespace std;
int inputArr[100'001];
//입력값받으면서 그대로 합 값 저장
int	Sum[100'001];

int N, M;
void Input() {
	int tmp1 = 0, tmp2 = 0;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> inputArr[i];
		//입력받자마자 바로 더해서 저장 pSum[i+1]은 i번째까지의 수를 다 더한 것
		Sum[i + 1] = Sum[i] + inputArr[i];
	}
	for (int i = 0; i < M; i++) {
		cin >> tmp1 >> tmp2;
		//인덱스 tmp1-1부터 tmp2-1까지의 합이므로 
		cout << Sum[tmp2] - Sum[tmp1-1]<<'\n';
	}
}

int main() {
	//입출력관련해서 시간 더 줄이기 위해
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

index i,j가 1씩 증가한것도 있고, Sum배열이 index-1번째까지의 수를 다 더한 값을 저장해서 좀 헷갈렸다.

그리고 모든 반복문마다 cin, cout함수를 사용했다보니 시간이 오래걸려서 시간초과가 나왔다.

c타입 입출력과 분리시키는
ios_base::sync_with_stdio(0);
cin과 cout연결 분리시키는
cin.tie(0);

함수들을 추가해줘야 시간안에 통과가 된다.