백준 15661 링크와 스타트

문제

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

15661번: 링크와 스타트

 

해당 문제는 브루트 포스 유형의 문제이다.

 

n명을 두팀으로 나눌 수 있는 총 가능한 방법을 생각해보면(이때 팀의 인원수는 같지 않아도 된다.)

1번 사람이 1번팀에 들어가는 경우, 2번팀에 들어가는 경우

2번 사람이 1번팀에 들어가는 경우, 2번팀에 들어가는 경우 

.

.

.

n번 사람이 1번팀에 들어가는 경우, 2번팀에 들어가는 경우 

 

총 경우의 수는 2^n 이다. 문제의 제한을 보면 n = 20 이고 2^20 = 1048576 이므로

브루트포스로 확인해봐도 괜찮다.

 

go(peopleNum, aTeam, bTeam) 함수에서 의미하는바는 아래와 같다

• peopleNum : peopleNum 번째 사람을 어떤 팀에 넣을지 결정하는 변수
• aTeam : 1번팀에 속한 사람의 번호가 들어있는 변수
• bTeam : 2번팀에 속한 사람의 번호가 들어있는 변수

브루트포스의 문제의 경우 

함수 호출 이전에 어떤 일을 했다면 함수 호출 종료 후에 원상태로 돌려주는 부분이 꼭! 필요하다.

 

코드

import java.util.*;

public class Main {
	static int [][] a;
	static int n, ans;

	static int go(int peopleNum, ArrayList<Integer> aTeam, ArrayList<Integer> bTeam) {
		if(peopleNum == n) {
			if(aTeam.isEmpty() || bTeam.isEmpty())
				return -1;
			
			int aScore = 0;
			for(int i = 0; i < aTeam.size(); i++) {
				for(int j = i; j < aTeam.size(); j++) {
					aScore += a[aTeam.get(i)][aTeam.get(j)];
					aScore += a[aTeam.get(j)][aTeam.get(i)];				
				}	
			}
			
			int bScore = 0;
			for(int i = 0; i < bTeam.size(); i++) {
				for(int j = i; j < bTeam.size(); j++) {
					bScore += a[bTeam.get(i)][bTeam.get(j)];
					bScore += a[bTeam.get(j)][bTeam.get(i)];
				}
			}
			
			return Math.abs(aScore - bScore);
		}
		
		int ans = Integer.MAX_VALUE;
		aTeam.add(peopleNum);
		int aScore = go(peopleNum + 1, aTeam, bTeam);
		if(aScore != -1) {
			ans = Math.min(ans,  aScore);
		}	
		aTeam.remove(aTeam.size()-1);
		
		bTeam.add(peopleNum);
		int bScore = go(peopleNum + 1, aTeam, bTeam);
		if(bScore != -1) {
			ans = Math.min(ans, bScore);
		}
		bTeam.remove(bTeam.size()-1);
		
		return ans;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		a = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				a[i][j] = sc.nextInt();
			}
		}
		
		ArrayList<Integer> aTeam = new ArrayList<>();
		ArrayList<Integer> bTeam = new ArrayList<>();
		
		System.out.println(go(0, aTeam, bTeam));
	}
}