[백준] 14889번 / Java / 스타트와 링크 - 재귀풀이

문제 - (https://www.acmicpc.net/problem/14889)

전형적인 조합문제였다. 서로다른 N개 중에 순서에 상관없이 C개를 뽑아낸 뒤 뽑은 것들로 능력치의 합을 구하고 뽑지 않은 나머지로 능력치의 합을 구한 뒤 뺀다. 뺀 값의 절댓값들 중 취소값이 정답!

이 문제를 제대로 풀어보려면 유튜브나 기술 블로그에서 조합을 구현하는 방법에 대해 공부해보면 좋을 듯 싶다

---

📌주의할 점

• 예를들어, 4명 중 2명(i, j)을 뽑는다면 능력치배열 S에서 능력치를 한번에 구할 수 있다. S[i][j] + S[i][j] = (i, j)가 팀일 때 능력치

• 단, 간과하지 말아야할 부분이 있는데 만약 6명중 3명을 뽑게되는 경우다 (왜냐면 문제에서 n명의 참가자 중 n/2명으로 두 팀 나눈다고 했으므로)
  예를들어, 123456 의 사람 중 123이 팀이 된다고 치면
  12 13 23 을 선택해서 S[1][2] + S[2][1] , S[1][3] + S[3][1] , S[2][3] + S[3][2] 를 계산해서 능력치의 합을 구해야 한다
  

• 123의 사람을 선택했다면 선택한 사람은 start팀 나머지 456은 link팀으로 나눠서 계산하면 한번에 능력치 합의 차를 구할 수 있다!

---

😅실수

예전에 종만북으로 조합 구현 공부할 때 했던 실수였다 ㅠㅠ

그림1 실수한 부분

바로 이 부분!!!

재귀 내부에서 순회를 위한 for문 구현 시, for문의 시작 인덱스를 0으로 해놓고 풀어버린 것

왜 이게 안되냐면 visited배열이 어떻게 표시되는지 확인해보면 이유를 알 수 있다

0,1 -> 0,2 -> 0,3 순으로 true가 되는데, 이제 백트래킹이 되면

1,0 -> 1,2 -> 1,3 이 되버린다. 0,1과 1,0은 동일하므로 배제해주지 않으면 시간초과 발생

 

😊해결방법

재귀함수 자체에서 파라미터를 넘길때 순회하고 있던 인덱스를 같이 넘겨주는것

그림1에서 answer(j, k+1) 처럼 하면 된다. 여기서 j는 for문의 인덱스고 k는 현재까지 선택한 사람의 수를 확인하는 용도다.

for문의 인덱스를 넘기게되면

0,1 -> 0,2 -> 0,3 에서 1로 넘어갔을 때, 1부터 시작하게 되므로

1,1(visited가 true이므로 continue) -> 1,2 -> 1,3 이 된다!

 

 

---

코드를 보려면 '더보기' 클릭

package boj.samsungSWtest;

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

/**
 * 40분 - 시간초과
 * 1시간30분 ... 도저히 모르겠음 ㅠㅠ
 * 해법확인함
 */
public class StartLink {
    static int n;
    static int[][] s;
    static boolean[] visited;
    static int answer = Integer.MAX_VALUE;

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

    static void answer(int idx, int k) {
        // 기저
        if (k == n / 2) {
            int start = 0;
            int link = 0;
            // visited가 true인 것들이 start팀, false인 것들은 link팀 이라고 한다
            for (int p = 0; p < n; p++) {
                if (visited[p]) {
                    for (int q = p + 1; q < n; q++) {
                        if (p == q) continue;
                        if (visited[q]) {
                            //System.out.println("start -> " + p + ", " + q);
                            start += (s[p][q] + s[q][p]);
                        }
                    }
                } else {
                    for (int q = p + 1; q < n; q++) {
                        if (p == q) continue;
                        if (!visited[q]) {
                            //System.out.println(" link -> " + p + ", " + q);
                            link += (s[p][q] + s[q][p]);
                        }
                    }
                }
            }
            //System.out.println("==============================");
            answer = Math.min(answer, Math.abs(start - link));
            return;
        }

        // 0으로 시작하면 1,2 -> 1,3 -> 1,4 -> 2,1 이 되버림 2,1과 1,2는 동일하므로 생략해줘야함
        for (int j = idx /* 0으로 시작하면 중복되는 경우가 많아짐 */; j < n; j++) {
            /* 조합풀때 이거때문에 애 많이 먹었으면서.. 또 같은 실수를 했구나... */
            if (visited[j]) continue;
            visited[j] = true;
            answer(j, k + 1);
            visited[j] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = stoi(br.readLine());

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

        visited = new boolean[n];
//        startTeam = new int[n / 2];
        answer(0, 0);

        System.out.println(answer);
    }
}