😥 첫 아이디어 & 실패
처음 이 문제를 접했을 때 가장 먼저 든 생각은 팀원이 이루어질 수 있는 경우를 구하고 그 안에서 점수를 각자 체첨 후 최소 점수를 배출해내야겠다고 생각했는데 굉장히 짧은 생각이었다.
정말 바보 같은 생각이었는데 하필 어느 정도 구현을 다하고 난 다음에 그걸 깨달았다 ㅠ
아래 코드는 직접 작성하면서 팀들을 다 구해보니...
애초에 1,2 1,3 1,4 2,3 2,4 3,4 이렇게 경우를 구해도 사실상..
1,2 = 3,4 이고 1,3 = 2,4 이다..즉 이럴 필요가 없었던 것이다.
🚨 이 점을 고치자!!
아이디어가 막상 생각나면 일단 해볼까? 싶은 마음보다는 정말 이게 맞나 하는 생각을 가지고 접근하는 것이 맞다!
import java.io.*;
import java.util.*;
public class Main {
static int n;
static int[][] abillitys;
static List<Integer> tempList = new ArrayList<>();
static int[] visited;
static Queue<List> squad = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
abillitys = new int[n][n];
visited = new int[n];
//입력 받기
for (int i = 0 ; i < n; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0 ; j < n; j++){
abillitys[i][j] = Integer.parseInt(st.nextToken());
}
}
makeSquad(0);
for(int i= 0 ; i < squad.size(); i++){
//System.out.println(squad.poll());
}
//능력치가 "최소"가 되도록 코드를 짜자
//받은 n에서 2등분이 되는 값을 기준삼아 2개의 팀으로 분할하여 그들의 합이 최소!
//n/2만큼 고르면 결국 나머지가 골라지니까 일단 막 골라볼까?
//근데 또 고민해야하는게 1,2 고르면 1,2 시너지 + 2,1시너즈
//일단 그 팀으로 조합 가능한 모든 경우를 뽑고 그 중 최소를 계산해볼까?..
//4팀이면 [1,2] [1,3] [1,4] [2,3] [2 4] [3 4]]
}
private static void makeSquad(int depth) {
//일단 그 팀으로 조합 가능한 모든 경우를 뽑고 그 중 최소를 계산해볼까?..
//4팀이면 [1,2] [1,3] [1,4] [2,3] [2 4] [3 4]]
//아..다 짜고 나니 사실상 1,2 = 3,4 잖아 바보냐? ㅋ른아ㅣ름달즈ㅏㄻ즤ㅠㅠㅠ
if(depth == 2){
//값을 한꺼번에 넣어주고 싶은데 그럼 값을 가지고 있을 배열을 하나 만들어야 하나 굳이?..
for(int j = 0 ; j < tempList.size(); j++)
System.out.print(tempList.get(j) + " ");
System.out.println();
squad.offer(tempList);
return;
}
for(int i= 0 ; i < n; i++){
if(visited[i] == 0){//아직 방문 안했다면
if(tempList.size() == 0) {
visited[i] = 1;
tempList.add(i + 1);
makeSquad(depth + 1);
tempList.remove(tempList.size() - 1);
visited[i] = 0;
}
else if(tempList.size() > 0 && tempList.get(0) < i+1){
visited[i] = 1;
tempList.add(i+1);
makeSquad(depth+1);
tempList.remove(tempList.size()-1);
visited[i] = 0;
}
}
}
}
}
결국..1시간 정도 더 고민을 하다가 정답을 찾아봤다.
애초에 생각한 것에 큰 틀은 벗어나지 않아서 다행이다! DFS를 통해서 팀을 구하고 팀을 구한 상태에서 차이값을 계산하는 건 맞는데..세세한 부분들이 너무 달랐다.
#DFS의 파라미터를 2개
#visited만을 이용
private static void makeSquad(int depth, int value) {
if (depth == n/2){
getDiff();
return;
}
for(int i = value; i < n ; i++){
visited[i] = 1;
makeSquad(depth+1, i+1);
visited[i] = 0;
}
}파라미터를 2개로 넘겨주고 방문여부만 체크하는 생각보다 엄청 간단한 로직..그리고 dfs의 특징인 if return으로 이루어져있었다.
반드시 최적의 {12,34} {13/24} {14/23}만을 구하기 위해 visited만을 관리하는 것이 인상에 남는다..막 어렵게 값 남기고 List사용하고 이럴 게 아니고 단순히 visited만으로도 체크할 수 있었다!!
어쨋든 팀을 이룰 때 모든 팀원들이 다 들어가니까 빠지는 팀원이 없다는 걸 좀 생각했어야했다..
성공 코드
성공했지만 결코 성공이 아니다..한 번 더 풀어봐야할 문제!
import java.io.*;
import java.util.*;
//1시간 정도 고민하다가 답지 참고
public class Main {
static int n;
static int[][] abillitys;
static int min = Integer.MAX_VALUE;
static int[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
abillitys = new int[n][n];
visited = new int[n];
//입력 받기
for (int i = 0 ; i < n; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0 ; j < n; j++){
abillitys[i][j] = Integer.parseInt(st.nextToken());
}
}
makeSquad(0,0);
System.out.println(min);
}
private static void makeSquad(int depth, int value) {
if (depth == n/2){
for(int i = 0; i < n ; i++){
System.out.print(visited[i]);
}
System.out.println();
getDiff();
return;
}
for(int i = value; i < n ; i++){
visited[i] = 1;
makeSquad(depth+1, i+1);
visited[i] = 0;
}
}
private static void getDiff() {
int start = 0;
int link = 0;
for(int i = 0 ; i < n-1; i++){
for(int j = i+1; j < n; j++){
if(visited[i] == 1 && visited[j] == 1){//start팀일 경우
start += abillitys[i][j];
start += abillitys[j][i];
}
else if(visited[i] == 0 && visited[j] == 0){//link팀일 경우
link += abillitys[i][j];
link += abillitys[j][i];
}
}
}
//팀 계산을 완료되면 최소 구하고
int val = Math.abs(start-link);
//가장 근접하는 건 0이니까 0 나오면 그냥 바로 종료~
if(val == 0){
System.out.println(val);
System.exit(0);
}
min = Math.min(min,val);
}
}
