IT/알고리즘
백준 14889 스타트와 링크
어센트
2020. 2. 26. 20:40
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
배운점
처음에 풀 때 팀조합 구성시 같은 팀 조합이 나오는것을 배제하지않아 자꾸 시간초과가 났었다.
그래서 중복된 팀 구성이 나오지 않게 하기위해 새로운 파라미터를 추가하여 문제를 해결했다.파라미터+1 인덱스 부터 팀을 구성하도록 하였다.
능력치를 계산할때 팀구성원으로 배열을 두개 만들어 그부분만 돌게하여 문제를 해결하려고 했지만 그냥 전체 이차원 배열을 순회하는 것과 시간차이가 크지않고 코드도 깔끔하게 짤 수 있다는 것을 배웠다.
|
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
63
64
|
package 백트래킹;
import com.sun.corba.se.impl.orbutil.CorbaResourceUtil;
import java.io.*;
import java.util.StringTokenizer;
public class 스타트와_링크 {
static int n;
static boolean [] visited;
static int [][] player;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
visited = new boolean[n+1];
player = new int[n+1][n+1];
for (int i = 1; i <=n ; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 1;j<=n;j++)
{
player[i][j] = Integer.parseInt(st.nextToken());
}
}
makeTeam(1,0);
System.out.println(min);
}
public static void makeTeam(int start,int depth){
if(depth == n/2){
min = Math.min(getAblity(),min);
return;
}
for (int i = start; i <=n; i++) {
if(!visited[i] ){
visited[i] = true;
makeTeam(i+1,depth+1);
visited[i] = false;
}
}
}
static int getAblity(){
int sumStart = 0;
int sumLink = 0;
for (int i = 1; i < n+1 ; i++) {
for (int j = 1; j < n+1 ; j++) {
if(visited[i] && visited[j]) // 둘다 스타트팀인 경우
{
sumStart+=player[i][j];
}
if(!visited[i] && !visited[j]) // 둘다 링크 팀인 경우
{
sumLink+=player[i][j];
}
}
}
return Math.abs(sumStart-sumLink);
}
}
|
cs |