[C] 백준 - 11659번: 구간 합 구하기 4

3월 21일(화) - 누적 합 (11659번)

11659번: 구간 합 구하기 4

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 최초로 주어지는 N개의 수를 저장할 배열인 num[100001 ]외에도, 구간 합을 구하기 위해서는

  누적 합을 저장하는 배열이 필요할 것 같다는 생각으로, sum[100001] 이라는 배열도 추가적으로 정의

- 반복문안에서 k=1부터 k=N까지 num 배열에 N개의 수를 입력받으면서,

  동시에 이전까지의 누적합인 sum[k-1]에 현재의 num[k]를 더한 값을 sum[k]에 저장한다

- 이렇게 k=1 부터 k=N까지의 각각의 누적 합을 저장해놓는다면,

   가장 마지막에 출력해야하는 i부터 j까지의 구간 합은 (j까지의 누적 합) - (i-1까지의 누적 합) 으로 구할 수 있을 것

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int main(void)
{
	int N, M, i, j;
	int num[100001];
	int sum[100001] = { 0, };

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

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

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ