문제 해석
- 문제는 일단 N과 NxN크기의 스타트링크장이 있다.
- 이 문제를 간략히 설명하자면 아래의 사진을 예시로 들 수 있다.
- 행렬이 가진 값들은 능력치 값이라고 보면 되고, 팀을 정할 때는 i열만 보고 숫자가 겹치지 않도록 짠 후, 능력치 계산은 i열 조합을 j으로 확장시켜 서로 역전시켜 더한 값으로 구하면 된다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static int minValue = Integer.MAX_VALUE;
public static int[][] iceRink;
public static int N;
public static boolean[] visit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
iceRink = new int[N][N];
visit = new boolean[N];
for(int i = 0; i < N; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; j++){
iceRink[i][j] = Integer.parseInt(st.nextToken());
}
}
br.close();
createTeam(0,0);
System.out.println(minValue);
}
public static void createTeam(int index, int fullDegree) {
if(fullDegree >= N/2){
gap();
return;
}
for(int i = index; i < N; i++){
if(!visit[i]){
visit[i] = true;
createTeam(i+1, fullDegree+1);
visit[i] = false;
}
}
}
static void gap(){
int start = 0;
int link = 0;
for(int i = 0; i < N-1; i++){
for(int j = i+1; j < N; j++){
if(visit[i] && visit[j]){
start += iceRink[i][j];
start += iceRink[j][i];
}
else if(!visit[i] && !visit[j]){
link += iceRink[i][j];
link += iceRink[j][i];
}
}
}
int differentValue = Math.abs(start-link);
if(differentValue == 0){
System.out.println(differentValue);
System.exit(0);
}
minValue = Math.min(differentValue, minValue);
}
}
결과
느낀 점
- 어휘력이 부족한지... 문제 해석부터 좀 오래걸린 문제이다. (결국 다른 분들 코드 보면서 작성했던 문제..)