백준 2003번 수들의 합2 (C++)

문제

2003번: 수들의 합 2

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

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

정답 코드

#include <iostream>
using namespace std;
int input[10001];
int sum_input[10001];
int main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	int n,m;
	cin >> n >> m;
	int start_idx = -1;
	for (int i = 0; i < n; i++){
		cin >>input[i];
		if (i != 0)
			sum_input[i] = sum_input[i - 1] + input[i];
		else 
			sum_input[i] = input[i];
		if (sum_input[i] >= m && start_idx == -1)
			start_idx = i;
	}
	int ret = 0;
	if (start_idx == -1){
		cout << ret <<"\n";
		return (0);
	}
	for (int i = start_idx; i < n; i++){
		int cnt = sum_input[i];
		for (int j = 0; cnt >  m ; j++){
			cnt = sum_input[i] - sum_input[j];
		}
		if (cnt == m)
			ret++;
	}
	cout << ret << "\n";
}

문제 풀이의 흐름

• 간단한 누적합 문제입니다.

• 입력을 받을 때 시작부터 끝까지 합을 계속해서 누적해서 더하는 배열을 만듭니다.

• 그 배열의 크기가 m값보다 커지는 인덱스를 먼저 가지고 시작합니다.

• 배열의 크기보다 더 작으면 0을 출력합니다,

• 그 이후에는 가장 큰 인덱스에서 이전의 합들을 하나씩 인덱스를 더해가며 빼줍니다,

• 그러면 사이의 값이 나오게 됩니다,

• 이 과정을 계속해서 반복합니다,

주의 할 점

누적합이 익숙치 않다면 어려울 수 있습니다.

반성 및 고찰

어렵진 않았습니다,

Uploaded by N2T