문제 링크

링크텍스트

문제 설명

입력

출력 은 문제링크로~~

문제 풀이

1. 팀 두개를 나눌 수 있는 모든 쌍을 구하고
2. 나눠졌으면 점수를 구하자

풀이는 아주 간단한데, 조합쌍을 구하는 방법에 대해 매개변수를 하나 다르게 했더니 너무나도 심한 결과 차이가 나와서 흥미로워서? 적었다..

차이가 있는 부분만 먼저 올리고 전체코드는 제일 아래쪽에 올리겠음!

재귀 1

	public static void dfs(int now, int count) {
		if(count == N / 2)
		{
			getSum();
			return ;
		}
		for(int i = now; i < N; i++) {
			if(!team[i]) {
				team[i] = true;
				dfs(now + 1, count + 1);
				team[i] = false;
			}
		}
	}
}

재귀 2

public static void dfs(int now, int count) {
		if(count == N / 2)
		{
			getSum();
			return ;
		}
		for(int i = now; i < N; i++) {
			if(!team[i]) {
				team[i] = true;
				dfs(i + 1, count + 1);
				team[i] = false;
			}
		}
	}

정답은 재귀2인데, 재귀1은 그냥 틀렸다. (마치 됬 이라는 글자가 존재하지 않는 것 처럼.. 돌려보니 중복된 조합도 뽑힘) 기억해두자 ㅜㅜ

적다보니까 안에서 for문이 더 만들어지는 그 구간을 알겠다.

재귀1은 첫번째 반복문은 정상적으로 도는데, 나중에 재귀가 끝나서 다시 갈길가다가 if(!visited[i])로 빠졌을때, 그때 진행중인 인덱스(i)를 넣어야지 과거에 비해 바뀌지 않은 now값을 지금와서 또 now에다가 넣고 돌리는 격이다.

진짜 극 의식흐름으로 써서 말이 좀 어려운데, 그냥 재귀에 약한 나에게 전하는 메모라고 생각하면 된다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[][] map;
	static int answer = 0;
	static boolean[] team;
	static int N;
	public static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		team = new boolean[N];
		map = new int[N][N];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}		
	}
	public static void dfs(int now, int count) {
		if(count == N / 2)
		{
			int startSum = 0;
			int linkSum = 0;
			for(int a = 0; a < N - 1; a++) {
				for(int b = a; b < N; b++) {
					if(team[a] && team[b]) {
						startSum += map[a][b] + map[b][a];
					}
					else if(!team[a] && !team[b]) {
						linkSum += map[a][b] + map[b][a];
					}
				}
			}
			answer = Math.min(answer, Math.abs(startSum - linkSum));
			if(answer == 0) {
				System.out.println(0);
				System.exit(0);
			}
			return ;
		}
		for(int i = now; i < N; i++) {
			if(!team[i]) {
				team[i] = true;
				dfs(i + 1, count + 1);
				team[i] = false;
			}
		}
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		init();
		
		dfs(0, 0);
		
		System.out.println(answer);
	}
}