알고리즘 분류

: 비트마스킹

최종 풀이

: 220906 화

https://www.acmicpc.net/source/48808448

최근 풀이 240124

• 동일한 cost 에 대한 처리를 안함.
  아래 놓친 부분을 읽고, 밑의 정리한 내용 공부 필요.
  https://www.acmicpc.net/submit/19942/72285621

놓친 부분 240124

아래 빨간 줄 내용에 대해서 생각해보면, cost 비용을 인덱스로 해서
second 값을 vector로 나열해야 하는 자료구조를 생각해야 함.

• 해결책
  : pair로 접근하는 방법이 있음.
  pair<int, vector> 이런식으로.

  핵심!

vecotr 에다가 pair 넣고 sort 하기.

: 아래 그림을 보면 sort 이전과 이후의 first 값 뿐아니라, second 값도
다르게 출력됨을 봐야 함.

알아야 할점.

https://velog.io/@kwt0124/map-vector-vectorvector-%EB%B3%80%ED%99%98
: mapping 중복 저장

이거 안됨...

https://www.acmicpc.net/submit/19942/47795525

반례

3

0 0 0 1

0 0 0 0 0

0 0 0 0 0

0 0 0 1 0

최근 첫번째 코드

• price값을 비교하는 방법으로 함.
  https://www.acmicpc.net/source/48808534

2번째코드

: 벡터에다가 다 집어놓고, 정렬하는 방법으로 하자.

문제점이 있음...
compare의 경우, 비교대상이 동일할 경우에 ,,,
반드시 false를 반환하거나, 아니면, 비교식을 통해서 반환을 해야함!

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

struct yori
{
	int mp;
	int mf;
	int ms;
	int mv;
	int price;
};

bool compare(vector<int>&a, vector<int>&b)
{
	//마지막 원소가 총합 price임 이걸로 비교해야 함.
	if (a[a.size() - 1] < b[b.size() - 1])
		return true;
	else if (a[a.size() - 1] == b[b.size() - 1])
	{
		//동일할 경우, 처리를 해야함. 
		//만약에 a의 사전순이 더 앞선다면, true
		// 아니면 b가 앞선다면 false;

		int mmmin = min(a.size(), b.size());
		bool cc = false;
		for (int i = 0; i < mmmin; ++i)
		{
			if (a[i] < b[i])
			{
				cc = true;
			}
		}

		// 같을 경우에 false로 반환해야 함... 
		return false;
		//모든 컨테이너의 
		//if (a[0] < b[0])
		//	return true;
		//else
		//	return false;
	}
	return false;
}


int main()
{
	int n;
	cin >> n;

	yori mmin;
	cin >> mmin.mp >> mmin.mf >> mmin.ms >> mmin.mv;

	int mmax = 0;

	vector<yori>v(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> v[i].mp >> v[i].mf >> v[i].ms 
			>> v[i].mv >> v[i].price;
		mmax += v[i].price;
	}

	//cout << "output" << endl;
	//for (int i = 0; i < n; ++i)
	//{
	//	cout <<  v[i].mp << ","<< v[i].mf << 
	//		"," << v[i].ms << "," << v[i].mv 
	//		<< "," << v[i].price;
	//	cout << endl;
	//}
	
	
	
	// 이차원 벡터를 사용해야 할 것 같다고 생각함.
	vector<vector<int>>res;
	//vector<int>res;

	// price를 빼로 4개를 확인해야 함.
	// 모든 경우의 수를 확인해야 하므로. 
	// 비트마스킹을 활용함.
	for (int i = 0; i < (1 << n); ++i)
	{
		yori test{0,0,0,0,0};
		vector<bool>check(n, false);
		//각각의 원소를 확인해야 함.
		for (int j = 0; j < v.size(); ++j)
		{
			// 1 2 3 4 5 6

			// 1로 하면 안됨.
			// 참일 경우에만 , 해당 자릿수가 1일 경우를 뜻함.
			if (i & (1 << j))
			{
				test.mf += v[j].mf;
				test.mp += v[j].mp;
				test.mv += v[j].mv;
				test.ms += v[j].ms;
				test.price += v[j].price;
				check[j] = true;
			}
		}

		// 최소 조건에 만족한다면 저장
		// 즉, mmin vs test를 비교해서 조건에 만족하면. 
		// 데이터를 저장해 놓자. 
		if (test.mf >= mmin.mf && test.mp >= mmin.mp
			&& test.mv >= mmin.mv && test.ms >= mmin.ms)
		{
			// 정렬해서 하기에는 복잡하니까.
			// price의 총합계를 비교하면서 컷팅하는 방법으로
			// 변경하자. 
			//if (mmax > test.price)
			//{
			//	// test.price가 동일할 경우, 사전순으로 출력이므로
			//	// 조건은 이렇게만 놓자.
			//	mmax = test.price;
			//	res.clear();
			//	for (int k = 0; k < v.size(); ++k)
			//	{
			//		if (check[k] == true)
			//		{
			//			res.push_back(k);
			//		}
			//	}
			//}

			//if (mmax > test.price)
			//{
			//	mmax = test.price;
			//}

			vector<int>tt;
			// 어떤 원소가 선택됬는지를 알아야 함.
			// 체크 불변수를 사용하자. 
			for (int k = 0; k < v.size(); ++k)
			{
				if (check[k] == true)
				{
					tt.push_back(k);
					//cout << k << " "; 출력용
				}
			}
			tt.push_back(test.price);
			res.push_back(tt);
			//cout << test.price << endl; 출력용
		}

		// 마지막에 sort를 해야 할듯함. 
		//그리고 2중 포문 안에서 진행되므로,
		// 컨테이너는 외부에서 선언하도록 하자.
	}

	// 2중 포문 출력해보자. 
	//for (int a = 0; a < res.size(); ++a)
	//{
	//	for (int b = 0; b < res[a].size(); ++b)
	//	{
	//		cout << res[a][b] << " ";
	//	}
	//	cout << endl;
	//}

	//cout << "sorting" << endl;

	sort(res.begin(), res.end() , compare);
	for (int a = 0; a < res.size(); ++a)
	{
		for (int b = 0; b < res[a].size(); ++b)
		{
			cout << res[a][b] << " ";
		}
		cout << endl;
	}

	if (res.size() == 0)
	{
		cout << -1;
	}
	else
	{
		cout << res[0][res[0].size() - 1] << endl;
		
		for (int i = 0; i < res[0].size() - 1; ++i)
			cout << res[0][i] + 1 << " ";
		// 이차원 배열의 첫번째 인덱스는 0이고,
		// 그 안의 벡터를 출력해야 함.

	}
	
}

최종코드

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

struct yori
{
	int mp;
	int mf;
	int ms;
	int mv;
	int price;
};

bool compare(vector<int>&a, vector<int>&b)
{
	//마지막 원소가 총합 price임 이걸로 비교해야 함.
	if (a[a.size() - 1] < b[b.size() - 1])
		return true;
	else if (a[a.size() - 1] == b[b.size() - 1])
	{
		//동일할 경우, 처리를 해야함. 
		//만약에 a의 사전순이 더 앞선다면, true
		// 아니면 b가 앞선다면 false;

		int mmmin = min(a.size(), b.size()) - 1;
		bool cc = false;
		for (int i = 0; i < mmmin; ++i)
		{
			if (a[i] == b[i])
				continue;
			return a[i] < b[i];
			//if (a[i] < b[i])
			//{
			//	cc = true;
			//}
		}

		// 같을 경우에 false로 반환해야 함... 
		//return false;
		//모든 컨테이너의 
		//if (a[0] < b[0])
		//	return true;
		//else
		//	return false;
	}
	return false;
}


int main()
{
	int n;
	cin >> n;

	yori mmin;
	cin >> mmin.mp >> mmin.mf >> mmin.ms >> mmin.mv;

	int mmax = 0;

	vector<yori>v(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> v[i].mp >> v[i].mf >> v[i].ms 
			>> v[i].mv >> v[i].price;
		mmax += v[i].price;
	}

	//cout << "output" << endl;
	//for (int i = 0; i < n; ++i)
	//{
	//	cout <<  v[i].mp << ","<< v[i].mf << 
	//		"," << v[i].ms << "," << v[i].mv 
	//		<< "," << v[i].price;
	//	cout << endl;
	//}
	
	
	
	// 이차원 벡터를 사용해야 할 것 같다고 생각함.
	vector<vector<int>>res;
	//vector<int>res;

	// price를 빼로 4개를 확인해야 함.
	// 모든 경우의 수를 확인해야 하므로. 
	// 비트마스킹을 활용함.
	for (int i = 0; i < (1 << n); ++i)
	{
		yori test{0,0,0,0,0};
		vector<bool>check(n, false);
		//각각의 원소를 확인해야 함.
		for (int j = 0; j < v.size(); ++j)
		{
			// 1 2 3 4 5 6

			// 1로 하면 안됨.
			// 참일 경우에만 , 해당 자릿수가 1일 경우를 뜻함.
			if (i & (1 << j))
			{
				test.mf += v[j].mf;
				test.mp += v[j].mp;
				test.mv += v[j].mv;
				test.ms += v[j].ms;
				test.price += v[j].price;
				check[j] = true;
			}
		}

		// 최소 조건에 만족한다면 저장
		// 즉, mmin vs test를 비교해서 조건에 만족하면. 
		// 데이터를 저장해 놓자. 
		if (test.mf >= mmin.mf && test.mp >= mmin.mp
			&& test.mv >= mmin.mv && test.ms >= mmin.ms)
		{
			// 정렬해서 하기에는 복잡하니까.
			// price의 총합계를 비교하면서 컷팅하는 방법으로
			// 변경하자. 
			//if (mmax > test.price)
			//{
			//	// test.price가 동일할 경우, 사전순으로 출력이므로
			//	// 조건은 이렇게만 놓자.
			//	mmax = test.price;
			//	res.clear();
			//	for (int k = 0; k < v.size(); ++k)
			//	{
			//		if (check[k] == true)
			//		{
			//			res.push_back(k);
			//		}
			//	}
			//}

			//if (mmax > test.price)
			//{
			//	mmax = test.price;
			//}

			vector<int>tt;
			// 어떤 원소가 선택됬는지를 알아야 함.
			// 체크 불변수를 사용하자. 
			for (int k = 0; k < v.size(); ++k)
			{
				if (check[k] == true)
				{
					tt.push_back(k);
					//cout << k << " "; 출력용
				}
			}
			tt.push_back(test.price);
			res.push_back(tt);
			//cout << test.price << endl; 출력용
		}

		// 마지막에 sort를 해야 할듯함. 
		//그리고 2중 포문 안에서 진행되므로,
		// 컨테이너는 외부에서 선언하도록 하자.
	}

	// 2중 포문 출력해보자. 
	//for (int a = 0; a < res.size(); ++a)
	//{
	//	for (int b = 0; b < res[a].size(); ++b)
	//	{
	//		cout << res[a][b] << " ";
	//	}
	//	cout << endl;
	//}

	//cout << "sorting" << endl;

	sort(res.begin(), res.end() , compare);
	//for (int a = 0; a < res.size(); ++a)
	//{
	//	for (int b = 0; b < res[a].size(); ++b)
	//	{
	//		cout << res[a][b] << " ";
	//	}
	//	cout << endl;
	//}

	if (res.size() == 0)
	{
		cout << -1;
	}
	else
	{
		cout << res[0][res[0].size() - 1] << endl;
		
		for (int i = 0; i < res[0].size() - 1; ++i)
			cout << res[0][i] + 1 << " ";
		// 이차원 배열의 첫번째 인덱스는 0이고,
		// 그 안의 벡터를 출력해야 함.

	}
	
}

---

알아야 할 점.

: map과 vector<vector>
가 어째서 이차원 벡터 형식으로 사용이 가능한지 알아보자.

첫번째 코드

#include <string>
#include <vector>
#include <iostream>
#include <tuple>
#include <map>
using namespace std;

struct jaeryo
{
	int m1;
	int m2;
	int m3;
	int m4;
	int cost;
};


int main()
{
	int n;
	cin >> n;

	// 같은 비용이 여러개일 경우, 사전순으로 가장 빠른 것이므로,
	// 정렬을 해야 함.
	jaeryo input;
	cin >> input.m1 >> input.m2 >> input.m3 >> input.m4;
	
	// tuple 보다는 struct를 사용하자. 
	map<int, jaeryo>m;

	for (int i = 0; i < n; ++i)
	{
		jaeryo j;
		cin >> j.m1;
		cin >> j.m2;
		cin >> j.m3;
		cin >> j.m4;
		cin >> j.cost;

		m.insert(make_pair(i , j));

	}
	/*
	for (auto iter : m)
	{		
		cout << "재료 : " << iter.first << " 번, ";
		cout << "단백질 : " << iter.second.m1;
		cout << "지방 : " << iter.second.m2;
		cout << "탄수화물 : " << iter.second.m3;
		cout << "비타민 : " << iter.second.m4;
		cout << "가격 : " << iter.second.cost;
		cout << endl;
	}
	*/

	// 최종 적으로 사용해야 할 변수는 
	// cost와 재료의 번호들의 수인데
	// 재료의 번호들이 2개일 수 있고, 3개 일 수도 있고,,
	map<int,vector<int>>result;

	// 비트마스킹으로 각 6개를 돌면서 
	// 만약에 조건에 일치할 경우
	// 벡터에다가 일단 넣자. 
	for (int i = 0; i < (1 << n); ++i)
	{
		// i를 가지고 모든 재료인 n과 
		// 각 원소가 1일 경우, 즉 해당 재료 사용 유무를
		// 체크하면서 sum을 계산

		jaeryo sum;
		sum.m1 = 0;
		sum.m2 = 0;
		sum.m3 = 0;
		sum.m4 = 0;

		vector<bool>check(n, false);

		int tempCost = 0;
		for (int j = 0; j < n; ++j)
		{
			// 각 원소에서 재료 선택 할까? 말까 체크 하는 부분
			if (i & (1 << j))
			{
				//해당 자리의 재료를 선택할 경우, 합을 구한다.
				sum.m1 += m[j].m1;
				sum.m2 += m[j].m2;
				sum.m3 += m[j].m3;
				sum.m4 += m[j].m4;
				check[j] = true;
				tempCost += m[j].cost;
			}
		}

		// 조건과 확인하자. 
		if (sum.m1 >= input.m1 && sum.m2 >= input.m2
			&& sum.m3 >= input.m3 && sum.m4 >= input.m4)
		{
			vector<int>kk;
			// cost 와 인덱스 번호를 하나의 벡터에다가 저장을
			// 해놓고,,,, cost가 가장 낮은 거를 기준으로 해서 
			// 정렬하자. 			
			for (int k = 0; k < check.size(); ++k)
			{
				if (check[k] == true)
				{
					
					kk.push_back(k);					
				}
			}

			result.insert(make_pair(tempCost, kk));

		}

	}
	
	if (result.empty())
		cout << "-1";
	else
	{
		


		// 전체 확인하기
		for (auto iter : result)
		{
			cout << "cost : ";
			cout << iter.first << endl;
			cout << " ";
		
			cout << "재료의 번호들 ";
			for (int i = 0; i < iter.second.size(); ++i)
			{
				cout << iter.second[i] + 1;
				cout << " ";
				//cout << ",";
			}
			cout << endl;
			//break;
		}
	}
	
	
}

-> 첫번째만 나오게 한다음에 출력함.
결과는 틀리다고 함... ㅡㅡ

• 반례가 있음
  

반례 드립니다. (게시글에 이미 있습니다.)
input :
3
0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
output :
0
3
answer :
0
1 2 3
사전순으로 앞서는 것을 출력해야합니다.

잘못 생각한 부분이 잇음.

: 만약에 tempCost의 값이 동일할 경우, 사전순으로 가장 빠른 것을
출력하라는 조건이 있음.
이를 코드에 적용하지 못해서 틀린 것임.

알아야 할점.

멀티맵을 통해서 풀려고 함.

• 코드

#include <string>
#include <vector>
#include <iostream>
#include <tuple>
#include <map>
#include <algorithm>
using namespace std;

struct jaeryo
{
	int m1;
	int m2;
	int m3;
	int m4;
	int cost;
};

//가장 작은 cost이므로 
int MAX = 987654321;


int main()
{
	int n;
	cin >> n;

	// 같은 비용이 여러개일 경우, 사전순으로 가장 빠른 것이므로,
	// 정렬을 해야 함.
	jaeryo input;
	cin >> input.m1 >> input.m2 >> input.m3 >> input.m4;

	// tuple 보다는 struct를 사용하자. 
	map<int, jaeryo>m;

	for (int i = 0; i < n; ++i)
	{
		jaeryo j;
		cin >> j.m1;
		cin >> j.m2;
		cin >> j.m3;
		cin >> j.m4;
		cin >> j.cost;

		m.insert(make_pair(i, j));

	}
	/*
	for (auto iter : m)
	{
		cout << "재료 : " << iter.first << " 번, ";
		cout << "단백질 : " << iter.second.m1;
		cout << "지방 : " << iter.second.m2;
		cout << "탄수화물 : " << iter.second.m3;
		cout << "비타민 : " << iter.second.m4;
		cout << "가격 : " << iter.second.cost;
		cout << endl;
	}
	*/

	// 최종 적으로 사용해야 할 변수는 
	// cost와 재료의 번호들의 수인데
	// 재료의 번호들이 2개일 수 있고, 3개 일 수도 있고,,
	multimap<int, vector<int>, greater<int>>result;

	// 비트마스킹으로 각 6개를 돌면서 
	// 만약에 조건에 일치할 경우
	// 벡터에다가 일단 넣자. 
	for (int i = 0; i < (1 << n); ++i)
	{
		// i를 가지고 모든 재료인 n과 
		// 각 원소가 1일 경우, 즉 해당 재료 사용 유무를
		// 체크하면서 sum을 계산

		jaeryo sum;
		sum.m1 = 0;
		sum.m2 = 0;
		sum.m3 = 0;
		sum.m4 = 0;

		// 불변수를 왜 생각했냐면? 
		// 벡터에 들어오는 값을 알기 위해서 사용함...
		//vector<bool>check(n, false);
		vector<int>kk;

		int tempCost = 0;
		for (int j = 0; j < n; ++j)
		{
			// 각 원소에서 재료 선택 할까? 말까 체크 하는 부분
			if (i & (1 << j))
			{
				//해당 자리의 재료를 선택할 경우, 합을 구한다.
				sum.m1 += m[j].m1;
				sum.m2 += m[j].m2;
				sum.m3 += m[j].m3;
				sum.m4 += m[j].m4;
				//check[j] = true;
				tempCost += m[j].cost;
				kk.push_back(j);
			}
		}

		// 조건과 확인하자. 
		if (sum.m1 >= input.m1 && sum.m2 >= input.m2
			&& sum.m3 >= input.m3 && sum.m4 >= input.m4)
		{	
			if (MAX >= tempCost)
			{
				MAX = tempCost;
				result.insert(make_pair(tempCost, kk));
			}			
		}		
	}

	//멀티맵은 인덱스 접근이 불가능함...

	

	if (result.empty())
		cout << "-1";
	else
	{	
		
		// 전체 확인하기
		for (auto iter : result)
		{
			cout << "cost : ";
			cout << iter.first << endl;

			cout << "재료의 번호들 ";
			for (int i = 0; i < iter.second.size(); ++i)
			{
				cout << iter.second[i] + 1;
				cout << " ";
				//cout << ",";
			}
			cout << endl;
			//break;
		}
	}


}

문제점.

1번 : second값 정렬을 해야하는데, multimap 자체만으로는 불가능함. 다른 stl을 덧붙여서 해야함.
2번 : cost 값이 0이므로 인덱스 0으로 접근하려고 했는데,,,
multi_map은 인덱스 접근이 안됨.....

해결책

: 중복이 있어서 multi_map을 사용하려고 했으나, 문제점들이 많음.
다른 방법을 사용하자.

최종 코드

#include <string>
#include <vector>
#include <iostream>
#include <tuple>
#include <map>
#include <algorithm>
#include <list>
using namespace std;

struct jaeryo
{
	int m1;
	int m2;
	int m3;
	int m4;
	int cost;
};

//가장 작은 cost이므로 
int MAX = 987654321;


int main()
{
	int n;
	cin >> n;

	// 같은 비용이 여러개일 경우, 사전순으로 가장 빠른 것이므로,
	// 정렬을 해야 함.
	jaeryo input;
	cin >> input.m1 >> input.m2 >> input.m3 >> input.m4;

	// tuple 보다는 struct를 사용하자. 
	map<int, jaeryo>m;

	for (int i = 0; i < n; ++i)
	{
		jaeryo j;
		cin >> j.m1;
		cin >> j.m2;
		cin >> j.m3;
		cin >> j.m4;
		cin >> j.cost;

		m.insert(make_pair(i, j));

	}
	/*
	for (auto iter : m)
	{
		cout << "재료 : " << iter.first << " 번, ";
		cout << "단백질 : " << iter.second.m1;
		cout << "지방 : " << iter.second.m2;
		cout << "탄수화물 : " << iter.second.m3;
		cout << "비타민 : " << iter.second.m4;
		cout << "가격 : " << iter.second.cost;
		cout << endl;
	}
	*/

	// 최종 적으로 사용해야 할 변수는 
	// cost와 재료의 번호들의 수인데
	// 재료의 번호들이 2개일 수 있고, 3개 일 수도 있고,,
	map<int, vector<vector<int>>>result;

	// 비트마스킹으로 각 6개를 돌면서 
	// 만약에 조건에 일치할 경우
	// 벡터에다가 일단 넣자. 
	for (int i = 0; i < (1 << n); ++i)
	{
		// i를 가지고 모든 재료인 n과 
		// 각 원소가 1일 경우, 즉 해당 재료 사용 유무를
		// 체크하면서 sum을 계산

		jaeryo sum;
		sum.m1 = 0;
		sum.m2 = 0;
		sum.m3 = 0;
		sum.m4 = 0;

		// 불변수를 왜 생각했냐면? 
		// 벡터에 들어오는 값을 알기 위해서 사용함...
		//vector<bool>check(n, false);
		
		vector<int>kk;
		//list<int>kk;
		int tempCost = 0;
		for (int j = 0; j < n; ++j)
		{
			// 각 원소에서 재료 선택 할까? 말까 체크 하는 부분
			if (i & (1 << j))
			{
				//해당 자리의 재료를 선택할 경우, 합을 구한다.
				sum.m1 += m[j].m1;
				sum.m2 += m[j].m2;
				sum.m3 += m[j].m3;
				sum.m4 += m[j].m4;
				//check[j] = true;
				tempCost += m[j].cost;
				kk.push_back(j);
			}
		}

		// 조건과 확인하자. 
		if (sum.m1 >= input.m1 && sum.m2 >= input.m2
			&& sum.m3 >= input.m3 && sum.m4 >= input.m4)
		{	
			if (MAX >= tempCost)
			{
				MAX = tempCost;
				//result.insert(make_pair(tempCost, kk));
				result[tempCost].push_back(kk);
			}			
		}		
	}

	//멀티맵은 인덱스 접근이 불가능함...

	

	if (result.empty())
		cout << "-1";
	else
	{	
		
		// 전체 확인하기
		//for (auto iter : result)
		//{
		//	cout << "cost : ";
		//	cout << iter.first << endl;
		//
		//	cout << "재료의 번호들 ";
		//	for (int i = 0; i < iter.second.size(); ++i)
		//	{
		//		cout << iter.second[i] + 1;
		//		cout << " ";
		//		//cout << ",";
		//	}
		//	cout << endl;
		//	//break;
		//}
	}


}