[BOJ] 11659번 | 구간 합 구하기 4 (C++)

🔗문제 보러가기

11659번: 구간 합 구하기 4

 

🧑‍💻풀이 과정

백준 사이트에서 단계별 풀어보기를 차례대로 정복 중인데, 그 중 누적 합이라는 유형에 대한 첫 문제였습니다.

문제를 보자마자 딱 생각난 것은, 통계학에서 쓰이는 누적분포함수(CDF, Cumulative Distribution Function)였습니다.

 

물론 개념적으로 완전히 동일한 것은 아니지만, 제 풀이의 기반 아이디어가 되어 주었습니다.

해당 아이디어를 토대로, 다음과 같이 문제를 순차적으로 풀 수 있습니다.

1. 주어진 N개의 숫자를 차례대로 누적하여 저장합니다.
   • 예를 들어, { 5, 4, 3, 2, 1 } 순서로 입력이 주어지면, { 5, 9, 12, 14, 15 }로 배열에 저장합니다. 
2. 주어진 구간 i, j에 대하여, arr[j] - arr[i-1]을 출력합니다.
   • 만약 i = 1인 경우라면, 처음 ~ j까지의 누적합이므로, arr[j]만 출력해주면 됩니다.

 

✏️소스 코드 및 결과

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

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

	int N, M;
	cin >> N >> M;

	vector<int> accumulatedSum(N + 1);
	cin >> accumulatedSum[1];
	
	for (int i = 2; i <= N; i++)
	{
		int number;
		cin >> number;
		accumulatedSum[i] = accumulatedSum[i - 1] + number;
	}

	for (int loop = 0; loop < M; loop++)
	{
		int i, j;
		cin >> i >> j;

		int Xj = accumulatedSum[j];
		int Xi = (i == 1) ? 0 : accumulatedSum[i - 1];

		cout << Xj - Xi << "\n";
	}

	return 0;
}