글 읽기 - 세용액 문제 제 알고리즘이 틀린건가요...?

chkwon91 9년 전 0

세용액 문제의 제 알고리즘이 틀린건지 알고싶습니다...

먼저 n개에 용액이 있다면 n개의 용액 두개를 섞어서 만들 수 있는 n*(n-1)/2개의 용액을 새로 생성한 후

원래의 용액과 새로 생성한 용액을 벡터에 넣어서 두 용액의 합의 절대값이 최소가 되는 경우로 구했습니다.

이때 걸러야 하는 경우의 수는 두개의 용액에 섞은 용액의 개수가 3개인지

그리고 중복된 경우가 없는지를 모두 테스트 했는데요

두개의 용액의 최소 절대값 문제는 중등부 문제에서 풀어서 제 알고리즘이 틀린 것 같지는 않습니다...

두 용액을 섞는 과정에서 5000*5000이라 메모리 초과가 일어 날것 같았는데

틀렸습니다가 나와서 좀 당황스럽습니다.

제 알고리즘에 어떤 부분이 틀린건가요...?

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

using namespace std;

struct solution
{
	int abs, neg;
	vector<int> v;
};

bool compare(solution a, solution b)
{
	return a.abs < b.abs;
}

int main()
{
	int n, tmp, ret = 2000000000;
	solution temp;
	vector<solution> data;
	vector<int> res_v;
	cin>>n;

	for(int clk = 0; clk < n; clk++)
	{
		cin>>tmp;
		if(tmp < 0)
		{
			temp.abs = -tmp;
			temp.neg = -1;
		}
		else
		{
			temp.abs = tmp;
			temp.neg = 1;
		}
		temp.v.push_back(tmp);
		data.push_back(temp);
		temp.v.clear();
	}

	int cur_size = data.size();
	for(int i = 0; i < cur_size - 1; i++)
	{
		for(int j = i+1; j < cur_size; j++)
		{
			tmp = data[i].abs*data[i].neg + data[j].abs*data[j].neg;
			if(tmp < 0)
			{
				temp.abs = -tmp;
				temp.neg = -1;
			}
			else
			{
				temp.abs = tmp;
				temp.neg = 1;
			}
			temp.v.push_back(data[i].abs*data[i].neg);
			temp.v.push_back(data[j].abs*data[j].neg);
			data.push_back(temp);
			temp.v.clear();
		}
	}

	//절대값의 크기로 정렬한다.
	sort(data.begin(), data.end(), compare);

	for(int piv = 0; piv < data.size() - 1; piv++)
	{
		int cur = data[piv].abs*data[piv].neg + data[piv+1].abs*data[piv+1].neg;
		cur = abs(cur);
		if(cur < ret && data[piv].v.size() + data[piv+1].v.size() == 3)
		{									//섞은 용액이 3개여야 한다.
	
		
			bool found = true;
			vector<int> t;
			for(int i = 0; i < data[piv].v.size(); i++)
				t.push_back(data[piv].v[i]);
			for(int i = 0; i < data[piv+1].v.size(); i++)
				t.push_back(data[piv+1].v[i]);

			//같은 용액끼리 섞이면 안되는 경우를 방지
			if(t[0] == t[1] || t[0] == t[2] || t[1] == t[2])
			{
				found = false;
			}

			if(found)
			{
				res_v = t;
				ret = cur;
			}
		}
	}

	sort(res_v.begin(), res_v.end());

	cout<<res_v[0]<<" "<<res_v[1]<<" "<<res_v[2]<<endl;

	return 0;
}

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

문제

문제

출처

ICPC

세용액 문제 제 알고리즘이 틀린건가요...?

chkwon91 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말