[백준 11659] 구간 합 구하기4

문제설명

해당 문제는 주어진 조건에 맞게 수를 입력 받은 뒤 구간 사이의 합을 구하여 출력시키는 문제이다.

 

알고리즘

1. N,M과 수의 값들을 각자 입력받는다

2. 수를 입력 받음과 동시에 그 전에 받은 값을 이용하여 합을 구한다

3. 구간을 입력 받으면 그 동시에 계산을 미리 해놓은 배열에서 빼서 시간을 단축시킨다

코드

#include <iostream>
#include <stdio.h>
using namespace std;

#define MAX 100001

int ans[MAX];//값을 받음과 동시에 합을 구함 

int main() {
	//입출력 시간 단축
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, M;
	cin >> N >> M;
	ans[0] = 0;
	for (int i = 1; i <= N; i++)//배열 값 받기
	{
		int num;
		cin >> num;	 			
		ans[i] = ans[i-1] +num;

	}
	for (int i = 0; i < M; i++) //구간 값 받기 및 결과 출력
	{
		int a, b;
		cin >> a >> b;
		cout << ans[b] - ans[a - 1] << "\n";
	}
}

고찰

이번 문제는 단순히 반복문을 사용하여 구간이 들어올때 마다 합을 구하면 시간초과가 발생한다.

따라서 값을 입력 받자마자 입력 받은 값 까지의 합을 구하여 저장할 수 있는 배열을 추가로 구현해야한다.

그리고 구간이 입력 될때마다 필요 없는 값은 빼서 바로 결과로 출력해야 해결 할 수 있다.