[백준/C & C++] 11659 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

C

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

int main()
{
	int n, m, input, a, b;
	scanf("%d %d", &n, &m);
	long long* sum = (long long*)malloc(sizeof(long long) * n);
	scanf("%d", &sum[0]);
	for (int i = 1; i < n; i++)
	{
		scanf("%d", &input);
		sum[i] = sum[i - 1] + input;
	}

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

	free(sum);
	return 0;
}

C++

#include <iostream>
#include <cstdlib>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, input, a,b;
	cin >> n >> m;
	long long* sum = new long long[n];
	cin >> sum[0];
	for (int i = 1; i < n; i++)
	{
		cin >> input;
		sum[i] = sum[i - 1] + input;
	}

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		if (a == 1) cout << sum[b - 1] << "\n";
		else if (a == b) cout << sum[b - 1] - sum[b - 2] << "\n";
		else cout << sum[b - 1] - sum[a-2] << "\n";
	}

	delete[]sum;
	return 0;
}

코드 설명

C와 C++ 모두 동적배열을 사용했다. 수의 개수 n, 합을 구해야 하는 횟수 m을 먼저 입력받는다. 이후 동적배열을 만든 다음에 반복문을 사용해서 n개의 수를 입력받는다. 이때 첫 번째 값은 반복문 바깥에서 먼저 입력받고, 두 번째 값부터 반복문 내에서 입력받으면서 이전의 값과 더한 값을 배열에 넣는다. 문제에서는 구간 합을 구하는 것이 목적이기에 누적 합을 사용한다. 아래 표에서는 우리는 sum[]를 이용해서 값을 구한다. 

 

ex) 

배열의 인덱스	0	1	2	3	4	5	6	7	8
입력된 수	2	4	6	8	10	12	14	16	18
sum[인덱스]	2	6	12	20	30	42	56	72	90

 

구해야 하는 횟수만큼 반복문을 돌면서 구간a, b를 입력받는다. 만약 a가 1이라면 sum[b-1]의 값을 출력한다. 그리고 a, b가 같을 경우에는 sum[b-1]-sum[b-2]을 출력한다.그 외의 경우에는 sum[b-1]-sum[a-2]를 출력한다.

 

반복문을 전부 다 돈 후에 sum배열을 해제하고 프로그램을 종료한다.

 

느낀 점

이전에 누적 합을 사용한 문제를 푼 적이 있어서 금방 생각해서 풀었다!