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

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

11659번: 구간 합 구하기 4

---

~~ 1 ~~

#include <stdio.h>  // 구간 합 구하기 4


int main()
{
	int n, m;
	scanf("%d %d", &n, &m);

	int arr[100001];
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}

	int ans[100001], sum = 0;
	for (int i = 0; i < n; i++)
	{
		sum += arr[i];
		ans[i] = sum;
	}

	for (int i = 0; i < m; i++)
	{
		int start, end;
		scanf("%d %d", &start, &end);

		if (start == 1)
		{
			printf("%d\n", ans[end - 1]);
		}
		else if (start == 2)
		{
			printf("%d\n", ans[end - 1] - ans[0]);
		}
		else
		{
			printf("%d\n", ans[end - 1] - ans[start - 2]);
		}
	}

	return 0;
}

~~ 2 ~~

#include <stdio.h>  // 구간 합 구하기 4


int main()
{
	int n, m;
	scanf("%d %d", &n, &m);

	int arr[100001];
	int ans[100001] = { 0, };
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &arr[i]);
		ans[i] = ans[i - 1] + arr[i];
	}

	for (int i = 0; i < m; i++)
	{
		int start, end;
		scanf("%d %d", &start, &end);
		printf("%d\n", ans[end] - ans[start - 1]);
	}

	return 0;
}

---

MEMO

[1]

-- 부분합에 대해서 개념을 구글링을 한 후 처음으로 구현

-- 입력받은 값들을 차례로 더한 값을 ans배열에 저장(index 예시: 1, 1 + 2, 1 + 2 + 3, ... 1 + 2 + ... end)

-- 처음이라서 그런지 뭔가 비효율적인 느낌이 들어서 구글링을 통해 보완

[2]

-- 더 간결하고 한눈에 잘 들어오는 것 같다

 

!! 부분 합 개념 숙지하기 !!