글 읽기 - 반례좀 부탁드립니다.. 고수님들

ds04030 3년 전 0

알고리즘은 다음과 같습니다.

1. 배열 A, B의 부분합으로 만들 수 있는 조합들을 sum_a, sum_b 배열에 저장

2. 중복을 포함하여 오름차순 정렬

3. sum_a의 왼쪽에서 부터, sum_b의 오른쪽에서 부터 투포인터로 합이 t가 되는 경우를 탐색

3-1. 합 > t : sum_b의 포인터 1 감소

3-2. 합 < t : sum_a의 포인터 1 증가

3-3. 합=t : sum_a, sum_b에서 중복되는 경우를 찾아서 반영

주저리 주저리 설명하였는데..

고수님들 알아봤으리라 믿습니다..

반례좀 찾아주십시오..하..제발

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

int n, m, t;
long long result = 0;
int A[1000], B[1000];
vector<long long> sum_a, sum_b;
void input();
void solve();
void make_sum();

int main()
{
	input();
	make_sum();
	solve();
	cout << result << "\n";
	return 0;
}

void input() {
	cin >> t;
	cin >> n;
	for (int i = 0; i<n; i++) cin >> A[i];
	cin >> m;
	for (int i = 0; i<m; i++) cin >> B[i];
}

void solve() {
	int p1 = 0, p2 = sum_b.size()-1;
	long long aLen = sum_a.size();

	while (p1<aLen && p2>=0) {
		long long sum = sum_a[p1] + sum_b[p2];
		if (sum == t) {
			long long temp = sum_a[p1];
			long long temp2 = sum_b[p2];
			int a = 0, b = 0;
			while (sum_a[p1] == temp) { 
				a++; p1++;
				if (p1 >= aLen) break;
			}
			while (sum_b[p2] == temp2) { 
				b++; p2--;
				if (p2 < 0) break;
			}
			result += (a*b);
		}
		else if (sum > t) {
			p2--;
		}
		else if (sum < t) {
			p1++;
		}
	}
}

void make_sum() {
	long long sum;
	for (int i = 0; i<n; i++) {
		sum = A[i];
		sum_a.push_back(sum);
		if (i == n - 1) break;
		for (int j = i + 1; j<n; j++) {
			sum += A[j];
			sum_a.push_back(sum);
		}
	}

	for (int i = 0; i<m; i++) {
		sum = B[i];
		sum_b.push_back(sum);
		if (i == m - 1) break;
		for (int j = i + 1; j<m; j++) {
			sum += B[j];
			sum_b.push_back(sum);
		}
	}

	sort(sum_a.begin(), sum_a.end());
	sort(sum_b.begin(), sum_b.end());
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례좀 부탁드립니다.. 고수님들

ds04030 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말