fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6.  
  7. int board[21][21] = { 0, };		//능력치 저장 보드
  8. int board_size;					//보드의 크기
  9. int low = 100;					//제일 적은 오차의 크기
  10. int flag[21] = { 0, };			//해당 인원의 소속 여부 확인용
  11. vector <int> start;				//start팀의 구성
  12. vector <int> link;				//link팀의 구성
  13.  
  14. void team(int a, int d)			//팀 선정 후 능력치 차이 확인
  15. {
  16. 	if (a == board_size / 2)	//link팀 선정 후 능력치 차이 확인
  17. 	{
  18. 		int S = 0;				//start팀의 총 능력치
  19. 		int L = 0;				//link팀의 총 능력치
  20.  
  21. 		for (int i = 1; i <= board_size; i++)
  22. 		{
  23. 			if (!flag[i]) link.push_back(i);	//팀에 소속하지않은 인원들을 link에 소속시키기
  24. 		}
  25.  
  26. 		for (int i = 0; i < board_size / 2; i++)
  27. 		{
  28. 			for (int j = 0; j < board_size / 2; j++)
  29. 			{
  30. 				S += board[start[i]][start[j]];		//start팀의 능력치 점수
  31. 				L += board[link[i]][link[j]];		//linck팀의 능력치 점수
  32. 			}
  33. 		}
  34.  
  35. 		if (abs(S - L) < low)		//능력치 점수의 차이
  36. 			low = abs(S - L);
  37.  
  38. 		if (!low)					//low값이 0이면 더이상 능력치 점수의 차이가 발생하지않는다는 것이기에 프로그램 종료
  39. 		{
  40. 			cout << low;
  41. 			exit(0);
  42. 		}
  43.  
  44. 		link.clear();				//link 벡터 전체 초기화
  45. 		return;
  46. 	}
  47.  
  48. 	for (int i = d; i <= board_size; i++)	//start팀만 소속 진행
  49. 	{
  50. 		if (flag[i]) continue;		//팀에 소속된 인원 제외
  51.  
  52. 		flag[i] = true;				//팀에 소속됨
  53. 		start.push_back(i);			//start팀에 소속
  54.  
  55. 		team(a + 1, i + 1);
  56.  
  57. 		start.pop_back();			//다른 인원 소속을 위해 제외
  58. 		flag[i] = false;			//팀에 소속이 안됨
  59. 	}
  60. }
  61.  
  62. int main(void)
  63. {
  64. 	ios::sync_with_stdio(false);
  65. 	cin.tie(NULL);
  66. 	cin >> board_size;
  67.  
  68. 	for (int i = 1; i <= board_size; i++)
  69. 	{
  70. 		for (int j = 1; j <= board_size; j++)
  71. 		{
  72. 			cin >> board[i][j];
  73. 		}
  74. 	}
  75. 	team(0, 1);
  76. 	cout << low;
  77. 	return 0;
  78. }
Success #stdin #stdout 0s 4940KB
comments (?)
stdin 
8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0
stdout 
1
https://ideone.com/wG96oF
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!