2018-04-09-1.md

문제

• 백준 온라인저지 14889번 - 스타트와 링크
• https://www.acmicpc.net/problem/14889

풀이

• 완전탐색을 통해서 모든 경우를 탐색해보고 그 안에서 차이가 최소인 값을 저장하고 출력하는 방식이다.
• DFS의 방법으로도 가능하지만 next_permutation을 통해서 조합을 이용해서 문제를 해결했다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>


using namespace std;

int n;
int a[20][20];
int min_diff=INT_MAX;

int main(){

	cin >> n;

	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> a[i][j];
		}
	}

	vector<int> c;

	// 1과 0을 각각 n/2씩 생성
	for(int i=0; i<n/2; i++){
		c.push_back(0);
	}
	for(int i=0; i<n/2; i++){
		c.push_back(1);
	}

	do{

		vector<int> ones;
		vector<int> zeros;

		for(int i=0; i<c.size(); i++){
			if (c[i]==1){
				ones.push_back(i);
			}
			else{
				zeros.push_back(i);
			}
		}

		int sum_ones=0, sum_zeros=0;

		for(int i=0; i<ones.size(); i++){
			for(int j=0; j<ones.size(); j++){
				
				if (i!=j){
					sum_ones += a[ones[i]][ones[j]];
				}

			}
		}

		for(int i=0; i<zeros.size(); i++){
			for(int j=0; j<zeros.size(); j++){
				
				if (i!=j){
					sum_zeros += a[zeros[i]][zeros[j]];
				}

			}
		}

		int diff = (sum_ones > sum_zeros) ? sum_ones - sum_zeros : sum_zeros - sum_ones;

		if (diff < min_diff){
			min_diff=diff;
		}

	}while(next_permutation(c.begin(),c.end()));

	cout << min_diff << '\n';

	return 0;
}

반성

• 다른 코드를 찾아보니 DFS를 통해서 모든 경우를 검색해보는 코드를 찾았다. 아래 첨부한다.

참고자료

• https://gist.github.com/fpdjsns/4d3de43a49fca55e1556e5ea515412b9