[백준 14889] 스타트와 링크(JAVA/C++)

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

14889번: 스타트와 링크

 

 

조합으로 한 팀을 뽑아서 체크해주는 방식으로 문제를 풀었다.(true면 start팀, false면 link팀)

C++로 풀었을 때는 굳이 벡터에 넣어서 계산했는데(7달 전에 푼거다..과거의 나보다 성장했음을 느낄 수 있었음 ㅎㅎ)

바로 값을 계산해서 답을 구하면 된다.

 

 

[JAVA]

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static int N,ans=987654321;
	static int[][] map;
	static boolean[] chk;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		map=new int[N][N];
		chk=new boolean[N];
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j]=sc.nextInt();
			}
		}
		dfs(1,0);
		System.out.println(ans);
		
	}
	private static void dfs(int index,int cnt) {
		if(cnt==N/2) {
			//System.out.println(Arrays.toString(chk));
			int start=0,link=0;
			for(int i=0; i<N; i++) {
				if(chk[i]==true) {
					for(int j=0; j<N; j++) {
						if(chk[j]==true) {
							start+=map[i][j];
						}
					}
				}else if(chk[i]==false) {
					for(int j=0; j<N; j++) {
						if(chk[j]==false) {
							link+=map[i][j];
						}
					}
				}
			}
			if(ans>Math.abs(start-link))
				ans=Math.abs(start-link);
			return;
		}
		if(index==N) {
			return;
		}
		chk[index]=true;
		dfs(index+1,cnt+1);
		chk[index]=false;
		dfs(index+1,cnt);
		
	}

}

 

 

 

[C++]

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

int N,M,minVal=987654321;
int map[21][21];
int team[21];

void Combination(int combArr[], int r, int index, int target) {
	if (r == 0) {
		memset(team, 0, sizeof(team));
		int startTeam = 0;
		int linkTeam = 0;
		vector <int> s;
		vector <int> l;
		for (int i = 1; i <= M; i++) team[combArr[i]] = 2;
		for (int i = 1; i <= N; i++) {
			if (team[i] == 2) s.push_back(i);
			else if (team[i] == 0)l.push_back(i);
		}
		//스타트팀 계산
		for (int i = 0; i < s.size(); i++) {
			for (int j = i + 1; j < s.size(); j++) {
				startTeam += map[s[i]][s[j]];
				startTeam += map[s[j]][s[i]];
			}
		}
		//링크팀 계산
		for (int i = 0; i < l.size(); i++) {
			for (int j = i + 1; j < l.size(); j++) {
				linkTeam += map[l[i]][l[j]];
				linkTeam += map[l[j]][l[i]];
			}
		}
		//차이값 구하기
		int result = abs(startTeam - linkTeam);
		if (result < minVal) minVal = result;
		
		
		return;
	}
	if (target == N+1) {
		return;
	}
	combArr[index] = target;
	Combination(combArr, r-1, index+1, target+1);
	Combination(combArr, r, index, target + 1);
}
int main() {
	cin >> N;
	for (int i = 1; i <= N; i++)for (int j = 1; j <= N; j++) {
		cin >> map[i][j];
	}
	M = N / 2;
	int combArr[11];
	Combination(combArr, M, 1, 1);
	cout << minVal;
	return 0;
}