The Grand Dinner/하기웅

소감 ¶

- algorithm 라이브러리 너무 좋음..ㅋㅋㅋ
- 한가지의 예외를 생각 못해 조금 헤맸음~

생각 ¶

- 가장 많은 사람이 있는 팀부터 가장 많은 자리가 있는 테이블부터 한명씩 배치시키면 된다.
- 그렇게 배치 시키다가 자리가 남지 않아 배치할 수 없는 순간이 오면 그 배치 뿐만 아니라 다른 어떤 방법으로도 배치가 불가능하다.
- 어느 한팀의 인원이 테이블의 수보다 많아버리면 무조건 배치가 불가능해진다.

[edit]

코딩 방법 ¶

- 팀의 이름표를 붙이고 그 상태에서 인원이 많은 순으로 정렬
- 테이블의 이름표를 붙이고 그 상태에서 자리가 많은 순으로 정렬
- 인원이 많은 팀부터 자리가 많은 테이블에 앉히면서 테이블에 앉을 수 있는 자리수를 감소 시키고 팀의 사람에게 테이블 번호를 부여
- 이렇게 되면 자리가 많은 테이블이 먼저 앉을 수 있는 자리가 0일 될 수는 없게된다.
- 앉히다가 테이블에 앉을 수 있는 자리의 수가 0인 테이블을 만나면 return false.
- 0을 만나지 않고 다 배치시키고 나면 '1'을 출력하고 사람에게 메겨진 테이블 번호의 작은 순으로 정렬 후 출력
- 0을 만나게 되면 '0'을 출력

[edit]

소스 ¶

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

int input1, input2;
int i, j;

struct Team {
	int number;
	int memberNum;
	int person[101];
};

struct Table {
	int number;
	int chairNum;
	int chair[101];
};

Team team[71];
Table nTable[51];

bool compareTeam(const Team &a, const Team &b)
{
	return a.memberNum>b.memberNum;
}

bool compareTeam2(const Team &a, const Team &b)
{
	return a.number<b.number;
}

bool compareTable(const Table &a, const Table &b)
{
	return a.chairNum>b.chairNum;
}

void printTeam()
{
	cout << "1" <<endl;
	for(i=1; i<input1+1; i++)
	{
		for(j=1; j<team[i].memberNum+1; j++)
			cout << team[i].person[j] << " ";
		cout <<endl;
	}
}

bool matchingTable()
{
	for(i=1; i<input1+1; i++)
	{
		for(j=1; j<team[i].memberNum+1; j++)
		{
			if(team[i].memberNum>input2)
				return false;
			if(nTable[j].chairNum>0)
			{
				nTable[j].chairNum--;
				team[i].person[j] = nTable[j].number;
			}
			else
				return false;
		}
		sort(&team[i].person[1], &team[i].person[team[i].memberNum+1]);
	}
	return true;
}

int main()
{
	while(cin >> input1 >> input2)
	{
		if(input1==0 && input2==0)
			break;
		for(i=1; i<input1+1; i++)
		{
			cin >> team[i].memberNum;
			team[i].number=i;
		}
		for(i=1; i<input2+1; i++)
		{
			cin >> nTable[i].chairNum;
			nTable[i].number=i;
		}
		sort(&team[1], &team[input1+1], compareTeam);
		sort(&nTable[1], &nTable[input2+1], compareTable);
		if(matchingTable())
		{
			sort(&team[1], &team[input1+1], compareTeam2);
			printTeam();
		}
		else
			cout << "0" <<endl;
	}
	return 0;
}