백준 실버 2- 백트래킹 ) 만족도 점수 16501

 

해당 문제를 이해하기까지에 조금 시간이 걸린 것 같았다 처음에 생각했을땐 2개씩 서로 평균값을 비교해서 

최소 값을 찾으면 되는줄 알았다 하지만 계속 보다보니 문제를 잘못 이해했다는걸 알았다

 

경기를 진행한다면 

첫번째 코트에 2대2 

두번째 코트에 2대2 

이런 상황이 올 것이다 

 

이것이 즉 한 게임이라고 가정하고 그 게임의 최소값 중 여러 조합을 백트래킹으로 돌면서

모든 게임을 다 체크하여 가장 큰 최소값을 찾아야하는 것이 이 문제의 핵심이다.

 

소수점 첫번째와 두번째를 체크하는 방법은 

(결과 값에 10을 곱한 값)  -  floor(결과 값에 10을 곱한 값) 이렇게 뺏을때 값이 0이라면 더 이상 두번째 소수점이

나오지 않는다는 것이기 때문에 이 조건을 생각해서 풀었다  

	#include <iostream>
	#include <climits>
	#include <cmath>
	
	using namespace std;
	
	
	float mins = 0.0;
	int arr[10];
	int visit[10];
	int num[10];
	
	void func(int t) {
		if(t == 8) {
			float sum = 0;
			float sum2 = 0;
			float sum3 = 0;
			float sum4 = 0;
			
			float ss = 1.0;
			
			sum += arr[0];
			sum += arr[1];
		
			sum2 += arr[2];
			sum2 += arr[3];
			
			
			sum /= 2.0;
			sum2 /= 2.0;
			
			sum3 += arr[4];
			sum3 += arr[5];
		
			sum4 += arr[6];
			sum4 += arr[7];
			
			sum3 /= 2.0;
			sum4 /= 2.0;
		
			ss = min(ss, float(1 - abs(sum - sum2) / 10.0));
			ss = min(ss, float(1 - abs(sum3 - sum4) / 10.0));
			
			mins = max(mins,ss);
				
			return;
		}
		
		for(int i = 0; i < 8; i++) {
			if(visit[i]) continue;
			
			arr[t] = num[i];
			visit[i] = 1;
			func(t+1);
			visit[i] = 0;
		}
	}
	
	int main() {
		
		for(int i = 0; i < 8; i++) {
			cin >> num[i];
		}
		
		func(0);
		
		cout << fixed;
		if((mins * 10) - floor((mins * 10))  == 0) {
			cout.precision(1);
		}
		else {
			cout.precision(2);
		}
		
		cout << mins;
		
	}