[백준][C] 2003번: 수들의 합 2

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

 

 

누적합을 이용하는 문제이다.

 

누적합이란 수열 A가 있을 때 S[i] = A[0] + A[1] + ... + A[i] 인 수이다.

 

이 누적합을 이용해 수열의 합을 여러번 구해야할 때 속도를 매우 빠르게 할 수 있다.

 

누적합에서 다음과 같은 식을 이끌어낼 수 있다.

1. A[i] = S[i+1] - S[i]
2. A[i] 부터 A[i + j] 까지의 합 = S[i + j] - S[i] + A[i]
   1. A[i+1] 부터 A[i + j] 까지의 합 = S[i + j] - S[i]

 

만약 위의 문제를 계산할 때 매 경우마다 합을 구해야한다면 시간복잡도는 매우 높아진다.

(밑의 코드에서 매번 합을 구한다면 시간복잡도는 O(N^3))

 

하지만 누적합을 이용한다면 O(1)로 구할 수 있게 된다.

 

따라서 누적합을 구해놓고 이중 for문을 돌려가며 모든 경우의 구간합을 구해가며 맞는 경우 개수를 세게 된다.

 

N = 10000 이고 시간 복잡도가 0.5초이므로 O(N^2) 알고리즘을 돌릴 경우 시간초과의 위험이 존재하나 모든 for 문이 N번 회전하지는 않으므로 0.5초 정도는 충분히 감당 가능할 것이다.

 

코드보기

#include <stdio.h> 
#pragma warning(disable:4996)

int A[10000];
int S[10000];

int main()
{
	int N, M;
	int left = 0, right = 0;
	int cnt = 0;
	int sum;

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

	scanf("%d", &A[0]);
	S[0] = A[0];
	for (int i = 1; i < N; i++)
	{
		scanf("%d", &A[i]);
		S[i] = S[i - 1] + A[i];
	}
	
	for (int i = 0; i < N; i++)
	{
		for (int j = i; j < N; j++)
		{
			sum = S[j] - S[i] + A[i];
			if (sum == M)
			{
				cnt++;
				break;
			}
		}
	}

	printf("%d\n", cnt);

	return 0;
}