[백준 16501] 만족도 점수 (C++)

https://www.acmicpc.net/problem/16501

 

문제

---

테니스 동호회 회장은 매주 참가 회원들이 만족할 만 하도록 2대 2 복식 조들을 짜야 한다. 각 회원은 참여한 게임이 대등하게 펼쳐졌을 수록 만족도가 높다. 참가 회원들의 실력 점수는 0 이상 10이하의 정수로 주어진다고 가정할 때, 한 경기에 참여한 회원의 만족도 점수는 다음과 같이 표현된다.

1 -  ( |상대 팀의 실력 점수 평균 - 본인 팀의 실력 점수 평균| / 10)

이 점수는 최악의 경우 0, 최상의 경우 1점을 범위로 갖는다. 

회장의 목표는 너무 불만족해 탈퇴하는 회원이 없도록 하는 것이다. 이를 위해 모든 회원들이 최소 1번은 참가하게 하고, 만족도 점수의 하한을 극대화 하고 싶다.

2개의 테니스 코트를 쓸 수 있고, 각 코트에서 한 게임씩만 할 수 있으며 8명의 회원이 참여한다고 하자. 목표에 맞게 조를 짰을 때, 만족도 점수의 하한을 구하는 프로그램을 작성하라.

 

입력

---

8명 회원의 실력 점수가 입력으로 주어진다. 점수는 공백으로 구분되어져 있다.

 

출력

---

첫째 줄에 만족도 점수의 하한을 출력한다.

정답이 정수 또는 소수점 한 자리의 실수로 표현할 수 있는 경우 소수점 첫째 자리까지, 두 자리의 실수로 표현할 수 있는 경우 소수점 둘째 자리까지 출력한다.

 

문제 풀이

---

8명이므로 브루트 포스로 모든 경우를 탐색한다.

next_permutation()이나 백트래킹을 사용하여 8명이 팀을 이룰 수 있는 모든 경우를 구한다.

첫번째와 두번째 사람이 팀을 이루고, 세번째와 네번째 사람이 팀을 이뤄서 이 두 팀이 경기를 한다고 정한다. 그리고 다섯번째와 여섯번째 사람이 팀을 이루고, 일곱번째와 여덟번째 사람이 팀을 이뤄서 두 팀이 경기를 한다.

문제의 조건에 맞게 모든 경우의 만족도를 구한 후, 두 만족도 중 작은 것의 최대를 구하면 된다.

 

c++의 경우에는 실수 형식이어도 1, 2와 같이 정수 값을 가진다면 소수점 없이 그대로 출력한다. 문제의 조건에 맞게 cout의 fixed와 precision()을 이용해 소수점 아래 첫째자리까지 출력하도록 한다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;
double* arr;
double*  team;
bool* isVisited;
double answer;

void backTracking(int depth)
{
	if (depth == 8)
	{
		double team1 = (team[0] + team[1]) / 2;
		double team2 = (team[2] + team[3]) / 2;
		double team3 = (team[4] + team[5]) / 2;
		double team4 = (team[6] + team[7]) / 2;
		double happy1 = (double)1 - ((abs(team1 - team2)) / 10);
		double happy2 = (double)1 - ((abs(team3 - team4)) / 10);
		answer = max(min(happy1, happy2), answer);
	}
	else
	{
		for (int i = 0; i < 8; i++)
		{
			if (isVisited[i] == false)
			{
				isVisited[i] = true;
				team[depth] = arr[i];
				backTracking(depth + 1);
				isVisited[i] = false;
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	answer = 0;
	arr = new double[8];
	team = new double[8];
	isVisited = new bool[8];
	for (int i = 0; i < 8; i++)
	{
		cin >> arr[i];
		isVisited[i] = false;
	}
	backTracking(0);
	cout << fixed;
	if (int(answer * 10) == answer * 10)
	{
		cout.precision(1);
	}
	else
	{
		cout.precision(2);
	}
	cout << answer << "\n";
	return 0;
}