[백준] 15661 링크와 스타트

1. 문제

www.acmicpc.net/problem/15661

15661번: 링크와 스타트

2. 접근방법

2개 숫자를 선택해서 합이 가장 작은 값을 구해야 한다.

N이 20개 뿐이라 부분집합을 전부 구해 모든 값에 대해 값을 구하면 쉽게 풀이 가능하다.

 

메모리제이션을 추가하면 더 빠르긴 하겠지만

부분집합만으로도 잘 풀리니 적용하진 않았다.

3. 자바 코드

package Silver;

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

public class P15661링크와스타트 {
	
	static boolean sel[];
	static int map [][],N;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		sel = new boolean[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());
			}
		}
		powerset(0);
		System.out.println(ans);
		
	}
	static int ans = Integer.MAX_VALUE;
	static void powerset(int idx) {
		if(idx == N) {
			int diff = calc();
			ans = Math.min(diff, ans);
			return;
		}
		sel[idx] = true;
		powerset(idx+1);
		sel[idx] = false;
		powerset(idx+1);
		
	}
	
	static int calc() {
		int linksum = 0,startsum = 0;
		
		for(int i = 0 ; i < N ; i++) {
			for(int j = 0 ; j < N ; j++) {
				if(sel[i] && sel[j]) linksum += map[i][j];
				if(!sel[i] && !sel[j]) startsum += map[i][j];
			}
		}
		return Math.abs(linksum-startsum);
	}

}

 

4. 마치며

명희님이 어렵다 한 문제.