👀 문제
https://www.acmicpc.net/problem/14889
👊 도전
풀이 방법 1
1. 설계
- 조합을 이용하여 만들 수 있는 팀의 경우의 수를 구한다.
- 팀의 능력치 차를 계산하여 작은 값을 min에 저장한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.util.Scanner;
/**
*
* @author HEESOO
*
*/
public class Main {
static int[][] team;
static boolean[] visit;
static int n;
static int min=Integer.MAX_VALUE;
public static void sum(){
int start=0;
int link=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(i==j) continue;
if(visit[i]&&visit[j]){
start+=team[i][j];
start+=team[j][i];
}
else if(!visit[i]&&!visit[j]){
link+=team[i][j];
link+=team[j][i];
}
}
}
int gap=Math.abs(start-link);
if(min>gap) min=gap;
}
public static void combination(int idx, int r){
if(r==n/2){
sum();
return;
}
for(int i=idx;i<n;i++){
if(!visit[i]){
visit[i]=true;
combination(i+1, r+1);
visit[i]=false;
}
}
}
public static void main(String[] args){
Scanner input=new Scanner(System.in);
n=input.nextInt();
team=new int[n][n];
visit=new boolean[n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
team[i][j]=input.nextInt();
}
}
combination(0, 0);
System.out.println(min);
}
}
3. 결과
🤟 성공 🤟
처음에 시간초과가 발생하여 sum()에서의 2중for문 범위가 커서 그런가 했는데, combination()을 재귀호출하는 부분의 파라미터를 combination(idx, r+1)로 했기 때문이다. 그래서 체크했던 사람을 또 확인하는 경우가 생겨 시간초과가 발생했었다.
4. 설명
- DFS를 이용한다.
- 팀을 나누는 방법은 순서 상관없이 뽑으면 되므로 조합과 같다.
- 따라서 팀을 나누기 위해 visit[]를 두어 true인 경우 start팀, false인 경우 link팀이라 가정한다.
- combination()에서 파라미터로 idx와 r을 넘긴다. 이때 idx는 이제 체크할 사람의 인덱스이고, r은 팀에 속한 사람 수이다. r이 n/2와 같아질 때, 두 팀이 짜여진 것이므로 sum()을 통해 두 팀의 능력치를 구하면 된다.
- 이때 파라미터로 넘기는 idx가 시간초과를 방지하는 역할을 하는데, 그 이유는 팀을 구성하는 사람의 순서에 상관없이 뽑기만 하면 되는 것이므로(1,2나 2,1이나 같다) 이전에 체크했던 사람을 또 확인하는 일은 없도록 하기 위함이다.
👏 해결 완료!
참고
- [백준] 14889번 스타트와 링크 https://whereisusb.tistory.com/139
- 백준 14889 스타트와 링크 Java https://dundung.tistory.com/100
- 백준 14889. 스타트와 링크 :: 돼지개발자 https://jaejin89.tistory.com/73