반응형
https://www.acmicpc.net/problem/14889
package com.company;
import java.util.Scanner;
public class StartAndLink_14889_me {
static int min_diff = Integer.MAX_VALUE;;
static int N;
static boolean[] ans;
static int[][] arr;
public static void main(String [] args){
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
arr = new int[N][N];
ans = new boolean[N];
for (int i=0; i<N; i++){
for (int j=0; j<N; j++){
arr[i][j] = sc.nextInt();
}
}
startLink(0, 0);
System.out.print(min_diff);
}
static void startLink(int idx, int count){
if(count == N/2){
int start_sum = 0;
int link_sum = 0;
for (int j=0; j<N-1; j++){
for (int k=j+1; k<N; k++){
if (ans[j] == true && ans[k] == true){
start_sum += arr[j][k];
start_sum += arr[k][j];
} else if (ans[j] == false && ans[k] == false){
link_sum += arr[j][k];
link_sum += arr[k][j];
}
}
}
int min_tmp = Math.abs(start_sum - link_sum);
if(min_tmp == 0){
System.out.print(0);
System.exit(0);
}
min_diff = Math.min(min_tmp, min_diff);
return;
}
for(int i = idx; i < N; i++) { // 이 부분 때문에 계속 시간초과 났었음
if(!ans[i]) {
ans[i] = true;
startLink(i + 1, count + 1); // 이 부분 때문에 계속 시간초과 났었음
ans[i] = false;
}
}
}
}
반응형
'Programming > Coding Test' 카테고리의 다른 글
피보나치 O(logN)으로 풀이 방법 (0) | 2022.05.29 |
---|---|
Arrays.sort(), StringBuilder 18870 좌표압축 (0) | 2021.12.04 |
백트래킹 알고리즘, 백준 2580 스도쿠 (0) | 2021.12.02 |
[알고리즘 정리] 벨만포드, 플로이드와샬 알고리즘 (0) | 2021.05.13 |
[알고리즘 정리] 다익스트라 알고리즘 (0) | 2021.05.10 |