브루트 포스 (3)

일부 경우만 해보기
모든 경우를 해보는 것과 다르게 절대 정답이 될 수 없는 경우는 확인하지 않을 수도 있다.

https://www.acmicpc.net/problem/2003
수들의 합 2

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int sum = 0;
		for (int j = i; j < n; j++) {
			sum += a[j];
			if (sum == m) {
				ans += 1;
				break;
			}
			if (sum > m) {
				break;
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/1806
부분합

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int n, s;
	cin >> n >> s;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int ans = n + 1;
	int sum = a[0];
	int left = 0;
	int right = 0;
	while (true) {
		if (sum < s) {
			right += 1;
			if (right == n) break;
			sum += a[right];
		}
		else {
			if (right - left + 1 < ans) ans = right - left + 1;
			sum -= a[left];
			left += 1;
			if (left == n) break;
			if (left > right) {
				right = left;
				sum = a[left];
			}
		}
	}
	if (n < ans) ans = 0;
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/1644
소수의 연속합

벡터가 비어있을 때 접근 시 런타임 에러 발생

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> prime;
	vector<bool> check(n + 1);
	for (int i = 2; i <= n; i++) {
		if (check[i] == false) {
			prime.push_back(i);
			for (int j = i + i; j <= n; j += i) {
				check[j] = true;;
			}
		}
	}
	if (prime.empty()) {
		cout << 0 << '\n';
		return 0;
	}
	int left = 0, right = 0;
	int ans = 0;
	int sum = prime[0];
	while (true) {
		if (sum < n) {
			right++;
			if (right == prime.size()) break;
			sum += prime[right];
		}
		else {
			if (sum == n) ans += 1;
			sum -= prime[left];
			left++;
			if (left == prime.size()) break;
			if (right < left) {
				right = left;
				sum = prime[left];
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

중간에서 만나기

• 문제를 절반으로 나눈 후, 양쪽 절반에서 모든 경우를 해본다.
• 탐색의 크기가 많이 줄어든다.
• 문제의 크기가 N인 경우 2^N에서 M = N/2 인 경우, 2^M + 2^M으로 줄어든다.

https://www.acmicpc.net/problem/1208
부분수열의 합 2
수열을 두개로 쪼개면 공집합이 2개 생긴다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n, s;
	cin >> n >> s;
	int m = n / 2;
	n = n - m;
	vector<int> up(n);
	vector<int> dn(m);
	for (int i = 0; i < n + m; i++) {
		if (i < n) cin >> up[i];
		else cin >> dn[i - n];
	}
	vector<int> up_s(1 << (n));
	for (int i = 0; i < (1 << n); i++) {
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {
				up_s[i] += up[j];
			}
		}
	}
	vector<int> dn_s(1 << m);
	for (int i = 0; i < (1 << m); i++) {
		for (int j = 0; j < m; j++) {
			if (i & (1 << j)) {
				dn_s[i] += dn[j];
			}
		}
	}
	sort(up_s.begin(), up_s.end());
	sort(dn_s.begin(), dn_s.end());
	long long ans = 0;
	n = (1 << n);
	m = (1 << m);
	int i = 0;
	int j = m - 1;
	while (i < n && j >= 0) {
		if (up_s[i] + dn_s[j] == s) {
			long long c1 = 1;
			long long c2 = 1;
			i += 1;
			j -= 1;
			while (i < n && up_s[i - 1] == up_s[i]) {
				i += 1;
				c1 += 1;
			}
			while (j >= 0 && dn_s[j] == dn_s[j + 1]) {
				j -= 1;
				c2 += 1;
			}
			ans += c1 * c2;
		}
		else if (up_s[i] + dn_s[j] < s) {
			i += 1;
		}
		else {
			j -= 1;
		}
	}
	if (s == 0) ans -= 1;
	cout << ans << '\n';
	return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n, s;
	cin >> n >> s;
	int m = n / 2;
	n = n - m;
	vector<int> up(n);
	vector<int> dn(m);
	for (int i = 0; i < n + m; i++) {
		if (i < n) cin >> up[i];
		else cin >> dn[i - n];
	}
	vector<int> up_s(1 << (n));
	for (int i = 0; i < (1 << n); i++) {
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {
				up_s[i] += up[j];
			}
		}
	}
	vector<int> dn_s(1 << m);
	for (int i = 0; i < (1 << m); i++) {
		for (int j = 0; j < m; j++) {
			if (i & (1 << j)) {
				dn_s[i] += dn[j];
			}
		}
	}
	sort(dn_s.begin(), dn_s.end());
	long long ans = 0;
	for (int i = 0; i < up_s.size(); i++) {
		auto p = equal_range(dn_s.begin(), dn_s.end(), s - up_s[i]);
		ans += p.second - p.first;
	}
	if (s == 0) ans -= 1;
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/2143
두 배열의 합

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int t, n, m;
	cin >> t;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cin >> m;
	vector<int> b(m);
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	vector<int> a_re;
	for (int i = 0; i < n; i++) {
		int sum = 0;
		for (int j = i; j >= 0; j--) {
			sum += a[j];
			a_re.push_back(sum);
		}
	}
	vector<int> b_re;
	for (int i = 0; i < m; i++) {
		int sum = 0;
		for (int j = i; j >= 0; j--) {
			sum += b[j];
			b_re.push_back(sum);
		}
	}
	sort(a_re.begin(), a_re.end());
	sort(b_re.begin(), b_re.end());
	long long ans = 0;
	for (int i = 0; i < a_re.size(); i++) {
		auto p = equal_range(b_re.begin(), b_re.end(), t - a_re[i]);
		ans += p.second - p.first;
	}
	cout << ans << '\n';
	return 0;
}

https://www.acmicpc.net/problem/7453
합이 0인 네 정수

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> a(n), b(n), c(n), d(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	vector<int> up, dn;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			up.push_back(a[i] + b[j]);
			dn.push_back(c[i] + d[j]);
		}
	}
	sort(dn.begin(), dn.end());
	long long ans = 0;
	for (int i = 0; i < up.size(); i++) {
		auto p = equal_range(dn.begin(), dn.end(), -up[i]);
		ans += p.second - p.first;
	}
	cout << ans << '\n';
	return 0;
}