글 읽기 - 반례 부탁드려요..

jinuu1208 6년 전 0

물론 예제 답안은 잘 나오구요..

중간에서 만나기? 방식으로 풀었습니다.

반례 부탁드려요 ㅜㅜ

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, a, b;
int a_p[1001] = { 0, }, b_p[1001] = { 0, };

vector<int> get_sum(int x, int x_p[])
{
	int sum = 0, j=0;
	vector<int> v;
	v.push_back(0);
	for (int i = 0; i < x; i++)
	{
		sum = x_p[i];//init sum
		if (sum <= n) v.push_back(sum);
		j = i + 1;
		if (j == x) j = 0;

		while (j != i)
		{
			sum += x_p[j];
			j++;

			if (sum <= n) v.push_back(sum);
			else if (sum > n) break;

			if (j == x) j = 0;
		}
	}
	return v;
}

int main()
{
	/////////////////////////////////////////////////
	// input
	cin >> n >> a >> b;

	for (int i = 0; i < a; i++)
		cin >> a_p[i];

	for (int i = 0; i < b; i++)
		cin >> b_p[i];

	/////////////////////////////////////////////////
	// 모든 경우 계산하여 벡터화
	vector<int> v_a = get_sum(a, a_p);
	vector<int> v_b = get_sum(b, b_p);
	sort(v_a.begin(), v_a.end());//a:오름차순
	sort(v_b.begin(), v_b.end());
	reverse(v_b.begin(), v_b.end());//b:내림차순
	////////////////////////////////////////////////////
	int ans = 0;
	int a_p = 0, b_p = 0, sum = 0;


	//cout << b;	
	while (a_p < v_a.size() && b_p < v_b.size())
	{
		sum = v_a[a_p] + v_b[b_p];

		if(sum==n)
		{
			int c_a = 1, c_b = 1;
			a_p++;
			b_p++;

			while (a_p< v_a.size() && v_a[a_p] == v_a[a_p - 1])
			{
				a_p++;
				c_a++;
			}

			while (b_p<  v_b.size() && v_b[b_p] == v_b[b_p - 1])
			{
				b_p++;
				c_b++;
			}
			//cout << a_p << ':' << b_p << endl;
			ans+=c_a*c_b;
		}
		else if (sum > n)
		{
			//cout << a_p << ':' << b_p << endl;
			b_p++;
		}
		else
		{
			//cout << a_p << ':' << b_p << endl;
			a_p++;
		}
	}

	if (n == 0) ans = 0;//n =0인 경우
	cout << ans << '\n';

	//system("pause");
	return 0;
}

cbs0615 6년 전 0

6 3 3

1 1 1 1 1 1

은 1이 출력되야하는데 위 코드는 9를 출력하네용

cbs0615 6년 전 0

get_sum함수를 보니까

모든 i 에 대해서 전체 피자 크기가 계속 중첩됩니당.

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

문제

문제

출처

ICPC

반례 부탁드려요..

jinuu1208 6년 전 0

cbs0615 6년 전 0

cbs0615 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말