백준(14889) - 스타트와 링크⭐

오늘 풀어본 문제는 ⭐스타트와 링크라는 문제이다.

1. 문제요약

• N개(짝수)의 사람이 있고. 이를 2팀으로 나눈다.
• N명의 사람은 1~N까지의 번호를 받았다. 그리고 서로가 같은 팀이 되었을 때의 능력치는 표에서 알 수 있다.
• 2팀의 능력치의 차가 최소가 되도록 하라.
• S12와 S21은 값은 같지만 2번 더해야 한다.

2. 입출력

[입력]

• N(4 ≤ N ≤ 20, N은 짝수)
• S내 값은 1이상 100 이하

3. 알고리즘

• 백트래킹/브루트포스

3.1 쌍의 총합을 통한 풀이

📍사람 i가 모든 사람과 맺는 관계의 전체 합.

즉, 다음은 i가 포함된 모든 i↔j 관계의 총합.
(Sij, Sji가 중복으로 들어갔음)

rowSum[i] = Σ S[i][j]
colSum[i] = Σ S[j][i]

weight[i] = rowSum[i] + colSum[i]

📍모든 능력치의 총합

totalSum <= Σ S[i][j]  (모든 i,j)

---

📍 실제 알고리즘

• 재귀함수로 현재 카운팅 된 사람 수, 마지막으로 추가된 사람의 번호, 현재까지 계산된 합을 넘겨줌
• 이때 1번째 사람이 팀에 들어간다는 가정을 하면, 더 빠른 가지치기가 가능함.

dfs(1, 1, total - rowSum[1] - colSum[1]);

static void dfs(int cnt, int last, int sum) {
        if (cnt == N / 2) {
            //rowSum+colSum은 중복된 값이 포함된 수임
            //즉 total에서 해당 값을 빼도 음수 나올 수 있음
            ANSWER = Math.min(ANSWER, Math.abs(sum));
            return;
        }
        if (N - last < N / 2 - cnt) {
            return;
        }

        for (int i = last + 1; i <= N; i++) {
            dfs(cnt + 1, i, sum - rowSum[i] - colSum[i]);
        }
    }

3.2 조합을 만드는 풀이

쌍의 합을 이용하는 게 아닌, 조합을 만들어 문제를 해결하는 방법이다.

        select[1] = true; // 1번 사람을 팀에 고정 -> 대칭성 경우의 수 제거 
        dfs(2, 1);                      

        System.out.println(ANSWER);
    }

    static void dfs(int idx, int cnt) {
        if (cnt == N/2) {
            calc();
            return;
        }
        if (idx > N) return;
        if (N - idx + 1 < N/2 - cnt) return;

        select[idx] = true;
        dfs(idx + 1, cnt + 1);
        select[idx] = false;
        dfs(idx + 1, cnt);
    }

    static void calc() {
        int A = 0, B = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
                if (select[i] && select[j]) {
                    A += S[i][j] + S[j][i];
                } else if (!select[i] && !select[j]) {
                    B += S[i][j] + S[j][i];
                }
            }
        }
        ANSWER = Math.min(ANSWER, Math.abs(A - B));
    }

❓처음 코드를 짤 때, 3.2번의 과정 속 dfs에서 for문을 하나 더 사용했었다.
다음과 같은 느낌이었다.

for (int i = idx; i <= N; i++) {
    select[i] = true;
    dfs(idx + 1, cnt + 1);  
    select[i] = false;
    dfs(idx + 1, cnt);
}

이는 왜 잘못된 판단이었을까?

사람 1 → 넣을지 말지
사람 2 → 넣을지 말지
사람 3 → 넣을지 말지

👉 각 단계에서 “후보가 딱 1명” → for문 필요 없음!

‼️위와 같은 코드가 필요한 경우는? → 이번 단계에서 여러 명 중 하나를 고르는 구조!
ex1) “n개 중 r개를 골라라”
ex2) “n개 중 정확히 k개 골라라”
ex3) “지금 위치에 올 수 있는 수가 여러 개”