백준 11659 구간 합 구하기 C/C++

구간 합 구하기 4 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

56016

23972

18527

41.297%

문제

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

입력

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

출력

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

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

예제 입력 1 복사

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력 1 복사

12
9
1

#include <iostream>
#include <string>

using namespace std;
int arr[1000001] = { 0 };
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n,m,sum=0,k,l;
	

	cin >> n>>m;
	for (int i = 0; i < n; i++)
	{
		cin >> sum;
		arr[i] += arr[i-1]+sum;
	}
	
	
	for (int i = 0; i < m; i++)
	{
		cin >> k >> l;
		printf("%d\n",arr[l-1]-arr[k-2]);
		
	}
	return 0;
}

 

그냥 이중 for문으로 돌리니까 시간 초과가 났다.

 

인덱스	0	1	2	3	4
배열A	5	4	3	2	1
합A	5	9	12	14	15

 

위처럼 구성할 수 있다.

동적계획법과 비슷한 것 같다.

 

합을 정해두고, 1~3의 합을 계산하면 미리 계산해둔 합 배열에서 인덱스 2번의 것을 추출하면, 그것이 합이 된다.

만약 2~4를 한다면, 4까지의 합이 인덱스 3에 있는 12이고 1까지의 합인 인덱스 0을 빼주면 된다

즉 14-5가 되어서 9를 출력할 수 있다.