[백준 자바 14889] 스타트와 링크 (실버 1)

 

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

 

전체 코드는 맨 마지막에 두었다.

문제를 풀기 전에 조합으로 팀을 나누고, 각 팀의 점수를 구한 뒤, 두 팀의 점수의 차 중 최솟값을 저장하면 되겠다 싶었다. 

 

근데 우선 조합 구현을 순열로... 하고 있었고, 또 나는 조합 구현을 백트래킹으로 했고, 매개변수로 총 점수 합을 가져가는 식으로 구현했는데 다 풀고 찾아보니 조합때는 팀 편성만 담당하고, 마지막에 다 편성이 되면 그때 점수를 구하는 형태로 구현을 해둬서 나도 수정 후 제출하니 380ms -> 280ms 로 100ms 아꼈다. ㅋㅋ 

 

---

 

 

 

이번에 풀 때는 입력을 받는 부분을 따로 빼서 input 메서드로 처리를 해봤다. 

우선 내 습관대로, 문제에서 쓰이는 전역 변수는 따로 static 으로 가장 상단부에 선언을 해둔다. 그리고 String to int 메서드도 만들어서  쓰는 편. 

출력이 최솟값이므로, Integer.MAX_VALUE 로 정수 최댓값으로 설정을 해두었다. 

 

 

그리고 main 에서는 입력, dfs, 정답 출력만 하도록 해봤다. 

인풋. 

 

그리고 팀편성을 하기 위해 조합을 사용했다. 순열과 조합 구현하는 부분은 왜 맨날 찾아보는 것 같지,, 

visited 가 true인 사람을 스타트팀으로, false를 링크팀으로 정해서 전체 팀원 수의 절반 (N / 2) 가 되면 팀편성이 완료되어 종료조건으로 정했다. 

 

 

 

마지막으로 팀 총 점수의 차를 구하는 부분이다. 

알고리즘 풀이 찾아보면서 알 수 없는 변수명을 조금 많이 극혐하는 편이라, 최대한 이해할 수 있도록 변수명을 지었다.. 

 

이중 for문에서 첫 for문은 모든 팀원을 돌면서 이 팀원이 스타트팀인지, 링크팀인지를 체크해두고, 

두 번째 for문에서는 0 인덱스 팀원부터 현재 팀원 직전까지 돌면서, 이전 팀원이 또 스타트팀인지 링크 팀인지 체크를 하고, 

 

둘 다 true 이거나 false 이면 (같은 팀이면), 먼저 점수를 계산해두고, 스타트 팀이면 스타트 팀 점수에, 링크팀이면 링크 팀 점수에 더해주도록 구현을 했다. 

 

마지막 if-else 문 좀 극혐인데 어떻게 더 개선하려고 고민을 많이 해봤는데 모르겠다..,.. 

 

마지막으로 두 팀간 점수차를 절대값으로 변환 후, 최솟값을 저장해두었다. 

 

 

 

 

---

 

 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int ans = Integer.MAX_VALUE;
    static int[][] scores;
    static boolean[] visited;

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws IOException {
        input();
        dfs(0, 0);
        System.out.println(ans);
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = stoi(st.nextToken());
        scores = new int[N][N];
        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int score = stoi(st.nextToken());
                scores[i][j] = score;
            }
        }
    }

    static void dfs(int depth, int start) {
        if (depth == N / 2) { // 팀 편성이 완료되면
            diff(); // 팀 스코어 차이를 계산 후 최솟값 저장
            return;
        }

        for (int i = start; i < N; i++) { // 조합 -> 순서 상관X
            if (!visited[i]) {
                visited[i] = true;
                dfs(depth + 1, i + 1);
                visited[i] = false;
            }
        }
    }

    static void diff() {
        int teamStartScore = 0;
        int teamLinkScore = 0;

        for (int nowPerson = 0; nowPerson < N; nowPerson++) {
            boolean isNowTeamStart = visited[nowPerson];

            for (int prevPerson = 0; prevPerson < nowPerson; prevPerson++) {
                boolean isPrevTeamStart = visited[prevPerson];

                if (isNowTeamStart == isPrevTeamStart) {
                    int tempScore = scores[nowPerson][prevPerson] + scores[prevPerson][nowPerson];

                    if (isNowTeamStart) {
                        teamStartScore += tempScore;
                    } else {
                        teamLinkScore += tempScore;
                    }
                }
            }
        }

        int scoreDiff = Math.abs(teamStartScore - teamLinkScore);
        ans = Math.min(ans, scoreDiff);
    }
}