Step-by-Step
[Java] 백준14889 - 스타트와 링크 본문
https://www.acmicpc.net/problem/14889
지문을 잘 읽은 후에 풀어야 한다고 느낀 문제!
예제 2번에서 6개의 팀원이 있을 때, 0,1,3번이 팀을 이룬다면
스타트팀은 해당 부분의 합으로 능력치로 결정된다.
자동으로 링크팀은 2,4,5번으로 해당 부분의 합이다.
Sii는 항상 0이기 때문에 i==j일때는 값을 더하지 않았고
스타트팀에 들어간 팀원은 ArrayList에 담아놓고 링크팀 계산에 엮기지 않도록 하였다.
package BOJ_SS;
import java.util.*;
public class boj14889 {
public static int[][] con;
public static int[] num;
public static int min = Integer.MAX_VALUE, n , sums;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
num = new int[n/2];
con = new int[n][n];
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++){
int k = sc.nextInt();
con[i][j] = k;
sums += k;
}
}
dfs(0, num, 0);
System.out.println(min);
}
public static void dfs(int cnt, int[] nums, int idx) {
if(cnt == n/2) {
int res = subs();
if(Math.abs(res) < min)
min = res;
return ;
}
for(int i=idx; i<n; i++) {
nums[cnt]=i;
dfs(cnt+1, nums, i+1);
}
}
public static int subs() {
int sum1=0, sum2=0;
ArrayList<Integer> concludes = new ArrayList<>();
for(int i=0; i<n/2; i++) {
for(int j=i+1; j<n/2; j++) {
int n1 = num[i];
int n2 = num[j];
sum1 += con[n1][n2];
sum1 += con[n2][n1];
if(!concludes.contains(n1))
concludes.add(n1);
if(!concludes.contains(n2))
concludes.add(n2);
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(i==j)
continue;
if(concludes.contains(i) || concludes.contains(j))
continue;
sum2 += con[i][j];
sum2 += con[j][i];
}
}
sum2/=2;
return Math.abs(sum2-sum1);
}
}
'언어 > JAVA' 카테고리의 다른 글
[Java] 백준14891 - 톱니바퀴 (0) | 2022.10.20 |
---|---|
[Java] 백준14890 - 경사로 (0) | 2022.10.20 |
[Java] 백준14888 - 연산자 끼워넣기 (0) | 2022.10.19 |
[Java] 백준1926 - 그림 (1) | 2022.09.23 |
[Java] 프로그래머스 - 주차 요금 계산 (0) | 2022.09.22 |
Comments