목차
1. 문제 설명
2. 푼 원리 설명
3. 코드
1. 문제 설명
https://www.acmicpc.net/problem/14889
14889번: 스타트와 링크
예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.
www.acmicpc.net
2. 푼 원리 설명
일단 나는 이거 답지 봤다.
(1) 팀을 조합으로 반으로 나눈다. -> (2) 각 팀 멤버간의 시너지 계산 -> (3) 차 구해서 그 차가 지금까지의 값 중 최소일 경우 갱신
요거까지는 생각을 했는데, (2)도 조합으로 스타트팀 내에서 2명씩 짝을 잡아서 값을 계산 해야 한다고 생각했다. 그러면 경우의 수가 기하급수적으로 늘어난다.
하지만 답을 보니, 시너지는 2명씩 짝을 지어서 그 둘 사이의 시너지만 다 더하는 것이 아니었고,
(나의 생각: A,B,C,D가 스타트 팀이면 A,B / C,D 로 짝 지어서 각 시너지 계산하고 그 시너지의 총합이 스타트팀의 총합 )
근데 이게 아니라 그냥 같은팀 멤버끼리 일어나는 모든 시너지의 총합이 답이었다.
(A,B,C,D가 스타트 팀이면 , A 와 B,C,D의 시너지, B 와 C,D의 시너지, C와 D의 시너지의 총합 )
-> 이걸 조합으로 구해야 한다고 생각했는데, 그냥 2차원 배열 돌면서 모든 시너지를 더하면 되었다.
3. 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.*;
// 14889번 스타트와 링크
public class Main {
// 사용할 기술: 조합
// 푸는 방법
// (A) 반으로 팀 나누기 -> 방문 배열로 갈라진 A팀, B팀 멤버 명시
// (B) A팀 총 시너지, B팀 총 시너지 계산 -> 각 팀별로 조합
// (C) 능력치 차이가 최소인지 확인, 현재까지 최소면 능력치 차이 변수 갱신
// * 입력 받기 위한 변수
static int N;
static int [][] arr;
// * 반 나누기 위한 방문 배열
static boolean [] isVisited;
// * 나눠진 팀용 -> 선수 담기/ 선수들의 방문 배열
// * 최소 시너지 차
static int subtraction = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1) 입력 받기
N = Integer.parseInt(br.readLine());
arr = new int[N+1][N+1];
isVisited = new boolean[N+1];
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
selectHalf(1,1);
System.out.println(subtraction);
}
// 2) 반으로 나누기
public static void selectHalf(int cnt, int start) {
if(cnt > N/2){
calculate();
return;
}
for (int i = start; i <= N; i++) {
if(!isVisited[start]){
isVisited[start] = true;
selectHalf(cnt+1, i+1);
isVisited[start] = false;
}
}
}
// true 팀에서 2명을 뽑아서 시너지를 계산한 후 tureTeamAmount에 집어넣는다.
// false 팀에서 2명을 뽑아서 시너지를 계산한 후 falseTeamAmount에 집어넣는다.
public static void calculate() {
int trueTeam = 0;
int falseTeam = 0;
for (int i = 1; i <= N -1 ; i++) {
for (int j = i+1; j <= N; j++) {
if( isVisited[i] && isVisited[j]){
trueTeam += arr[i][j] + arr[j][i];
}
if(!isVisited[i] && !isVisited[j]){
falseTeam += arr[i][j] + arr[j][i];
}
}
}
subtraction = Math.min(subtraction, Math.abs(trueTeam - falseTeam));
}
}
'알고리즘 > 문제 풀이' 카테고리의 다른 글
💔 백준 2503 숫자야구 JAVA (0) | 2024.04.07 |
---|---|
💚 5430 AC JAVA (0) | 2024.03.09 |
💜 2589 보물섬 (0) | 2024.03.06 |
💜 2667번 단지 번호 붙이기 JAVA (0) | 2024.03.02 |
💜 2606 바이러스 JAVA (0) | 2024.02.29 |