C++ / 백준 / 2003 / 수들의 합 2

문제

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

2003번: 수들의 합 2

문제풀이

메모이제이션을 이용했다.

idx는 0부터 N-1까지, idx2는 idx부터 N-1까지로 둔다.

idx는 더하려는 첫 번째 원소, idx2는 더하려는 마지막 원소이다.

따라서 idx부터 idx2까지 더한 값을 구하고, M인지 판별을 한다.

각각의 값은 자연수이므로 sum이 M을 넘어가면 더할 때마다 무조건 커지므로 효율성을 위해 break를 한다.

모든 경우의 수를 판별하였으면 answer을 출력한다.

 

코드

#include <iostream>
#include <vector>
using namespace std;
int N, M;

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

	cin >> N >> M;
	int idx(0);
	int idx2(0);
	int answer(0);
	vector<int>seq(N, 0);

	for (idx = 0; idx < N; ++idx)
		cin >> seq[idx];

	for (idx = 0; idx < N; ++idx) {
		int sum(0);
		for (idx2 = idx; idx2 < N; ++idx2) {
			sum += seq[idx2];
			if (sum == M) {
				++answer;
				break;
			}
			else if (sum > M) break;
		}
	}
	cout << answer;
}