Notice
Recent Posts
Recent Comments
Link
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
Tags
more
Archives
Today
Total
관리 메뉴

자이의 프로그래밍

스타트와 링크 본문

Algorithm/Cases-Study

스타트와 링크

Xi_kor 2021. 7. 10. 08:34

이것도 마찬가지로 순열을 이용했다.

일단 입력을 받은 후 0인 팀과 1인 팀으로 절반씩 나눠서 벡터에 push해주었다. 그리고 정렬을 한 뒤, next_permutation으로 모든 경우를 찾으면서 start 팀과 link 팀의 점수를 구해주었다. 그리고 차잇값이 가장 적은 값으로 갱신해주었다. 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <cmath>
using namespace std;
int s[25][25];

int main(){
	int n;
	cin>>n;
	
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin>>s[i][j];
		}
	}
	
	vector <int> d;
	for(int i=0; i<n; i++){
		if(i<n/2) d.push_back(0);
		else d.push_back(1);
	}
	sort(d.begin(), d.end());
	int ans=2147000000;
	
	do{
		int a1=0;
		int a2=0;
		
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(d[i]==d[j]&&d[i]==0) a1+=s[i][j];
				else if(d[i]==d[j]&&d[i]==1) a2+=s[i][j];
			}
		}
		
		int val=abs(a1-a2);
		if(val<ans) ans=val;
	}while(next_permutation(d.begin(), d.end()));
	
	cout<<ans;
	return 0;
}

'Algorithm > Cases-Study' 카테고리의 다른 글

맞춰봐  (0) 2021.07.10
단어수학  (0) 2021.07.10
가장 먼 노드  (0) 2021.06.29
더 맵게  (0) 2021.06.29
점프 1890  (0) 2021.05.13