[Baekjoon/백준] 11659번: 구간 합 구하기 4(C/C++)

단계별로 풀어보기 17단계(누적 합) 1번 문제

https://www.acmicpc.net/step/48

누적 합 단계

---

백준 11659번: 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

---

문제 설명

수 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

---

접근 방법

이번 문제는 숫자 개수 N과 구간 합을 구할 횟수 M을 입력받고 N개의 숫자와 M 구할 구간 범위를 입력해 각 구간의 합을 출력하는 문제다.

조금 이상하게 썼지만 간단히 얘기해서 N개의 숫자로 이뤄진 배열에서 배열 인덱스 두개를 입력해서 두 배열 인덱스 범위 내의 숫자 합을 출력하면 된다.

단순히 생각하면 그냥 인덱스 i j에 해당하는 배열들을 반복문으로 다 더해도 되겠지만, 배열 크기와 구할 숫자가 크므로 일일이 다 반복문을 하기에는 시간 초과가 발생할 것이다.

일단 문제에서 요구하는 것은 배열의 구간 합이다. 즉 배열에 어떤 값이 있던 상관 없다. 따라서 배열에 숫자를 계속해서 누적해서 배열에 저장하여 i번째 인덱스와 j번째 인덱스의 값을 빼기만 하면 문제를 해결할 수 있다.

---

코드

#include <iostream>
using namespace std;
#define MAX 100001

int num[MAX];

int main(int argc, char * argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, M, inputNum = 0, i, j;
	cin >> N >> M;

	for (int h = 1; h < N + 1; h++) {
		cin >> inputNum;
		num[h] = num[h - 1] + inputNum;
	}

	for (int h = 0; h < M; h++) {
		cin >> i >> j;
		cout << num[j] - num[i - 1] << "\n";
	}

	return 0;
}

---

결과

백준 제출 결과

마지막 출력에서 endl을 썼다가 시간 초과가 발생했다.