[C언어] 백준 11659번 구간 합 구하기

 

링크

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

 

예제 입력 1

---

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

 

예제 출력 1

---

12

9

1

 

 

 

아이디어 스케치

---

- 배열을 생성하여 배열의 인덱스 별로 값을 입력 받고, 단순히 주어지는 인덱스 값의 범위에 해당하는 배열값을 더하면 시간초과가 발생한다.
- 대표적인 누적 합 알고리즘을 이용하는 문제이다.

 

 

 

코드 분할 설명

---

 

scanf("%d %d", &N, &M);

	arr = (int*)calloc(N+1, sizeof(int));
	sum = (int*)calloc(N+1, sizeof(int));

 

- 수 N개를 저장할 배열(arr)과 누적 합을 저장할 배열(sum)을 calloc으로 동적할당 => 배열값을 0으로 초기화까지 해줌
- 이 문제에서는 배열의 인덱스가 0부터 시작하지 않고 1부터 시작하므로 N+1개 만큼의 공간을 할당해줌

 

 

 

for (int i = 1; i <= N; i++) {
		scanf("%d", &arr[i]);
		sum[i] += sum[i-1] + arr[i];
	}

 

- 현재 calloc으로 동적할당 되어있으므로 sum[0]=0으로 초기화 되어있음
- sum[i]는 i번째 인덱스 까지의 누적 합으로
  sum[1] = sum[0]+arr[1]
  sum[2] = sum[1]+arr[2]
  sum[3] = sum[2]+arr[3]
  이런식으로 sum[i]에는 i번째 인덱스 까지의 누적합이 저장된다.

 

 

 

for (int i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		printf("%d\n", sum[b]-sum[a-1]);
	}

 

- 이 코드는 인덱스의 범위를 입력받아 이 인덱스 범위 내에 해당하는 배열의 합을 구하는 코드이다.
- 여기서 중요한 부분은 sum[b]-sum[a-1] 부분인데 a-1을 한 이유를 간단하게 생각해보면 1 2 3 4에서 2부터 4까지의 합을 구하려면 4(10)-2(3)을 하는 것이 아닌 4(10)-1(1)을 해야지 해당하는 범위의 누적 합이 구해지므로 a-1을 하는 것 이다.

 

 

 

 

전체 코드

---

#include <stdio.h>
#include <stdlib.h>

int main()
{
	int N, M;
	int* arr;
	int* sum;
	int a, b;

	scanf("%d %d", &N, &M);

	arr = (int*)calloc(N+1, sizeof(int));
	sum = (int*)calloc(N+1, sizeof(int));

	for (int i = 1; i <= N; i++) {
		scanf("%d", &arr[i]);
		sum[i] += sum[i-1] + arr[i];
	}

	for (int i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		printf("%d\n", sum[b]-sum[a-1]);
	}

	free(arr);
	free(sum);

	return 0;
}

 

 

 

 

 

제출 결과

---