📖 문제

문제 링크

💡 아이디어

1. 팀을 나눴을 때 각 팀의 능력치를 구하는 방법

위와 같이 능력치가 나눠졌을 때, 1, 2번이 한 팀이라면 총 능력치는 (1,2) 와 (2,1) 의 값을
더한 것과 같다.

만약 n=6이어서 1, 2, 3번이 한 팀이라면 총 능력치는 (1,2), (2,1), (1,3), (3,1), (2,3), (3,2) 의 값을 더한 것과 같다.
잘 보면 (i,j) 순서쌍은 n명의 팀원 중 순서에 상관 없이 2명을 고르는 경우의 수와 추가로 각 경우의 수에서 i와 j의 위치가 바뀐 것임을 알 수 있다.

3명중 2명을 고르는 순서쌍: (1,2), (1,3), (2,3)
그 순서쌍들의 i,j위치가 바뀐 것: (2,1), (3,1), (3,2)

2. 팀을 나누는 방법

총 n명의 사람이 있다면, 1번부터 n번까지 각 사람을 스타트팀에 포함시킬 것인지 아닌 것인지를 결정하는 방법이 있다. 이 경우 자연스럽게 다음과 같은 이진 트리를 만들 수 있다.

트리 형태로 탐색할 수 있다면 자연스럽게 백트래킹을 사용하는 것을 떠올릴 수 있다.

백트래킹

백트래킹을 사용하려면 '이전 상태를 어떻게 저장할 것인가?'를 먼저 생각해야 한다. 이 경우 저장해야 하는 상태는 다음과 같다.

i번째 사람을 골랐는가, 안 골랐는가?

참, 거짓의 형태로 저장할 수 있는 상태이므로, 길이가 n인 bool 배열을 사용하면 적절할 것 같다.

스타터팀을 모두 고르면, 고르지 않은 모든 사람이 링크팀이기 때문에 링크팀을 고르는 경우는 생각하지 않아도 된다.

3. 탐색 종료 조건(백트래킹 조건)

1. 만약 고른 사람의 수가 n/2와 같다면 스타트팀에 포함될 사람을 모두 고른것이기 때문에 각 팀의 능력치를 계산한 후, 그것이 최솟값인지 확인하면 된다.

2. 만약 고른 사람의 수가 n/2보다 작은데 탐색할 사람의 번호가 n보다 커진다면 더 이상 사람을 고를 수 없으므로 종료한다.

✏️ 코드

use std::cmp::{max, min};
use std::io::{stdin, Read};

fn main() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace().flat_map(str::parse::<usize>);

    let n = input.next().unwrap() as usize;
    let mut abilities: Vec<Vec<usize>> = vec![vec![0usize; n]; n];
    // 능력치 테이블 생성
    for r in abilities.iter_mut() {
        for c in r.iter_mut() {
            *c = input.next().unwrap();
        }
    }

    let mut minimum = usize::MAX;
    let mut picks = vec![false; n];
    pick_or_not(n, 0, 0, &mut picks, &abilities, &mut minimum);
    println!("{minimum}");
}

fn pick_or_not(n: usize,
               index: usize,
               pick_count: usize,
               picks: &mut Vec<bool>,
               abilities: &[Vec<usize>],
               minimum: &mut usize) {
    // 종료조건: 스타터팀을 모두 고른 경우
    if pick_count == n/2 {
        // 팀 나누기
        let mut team_start: Vec<usize> = Vec::new();
        let mut team_link: Vec<usize> = Vec::new();
        for i in 0..n {
            if picks[i] {
                team_start.push(i);
            } else {
                team_link.push(i);
            }
        }
        // 각 팀의 능력치 구하기
        let mut ability_start = 0usize;
        let mut ability_link = 0usize;
        for i in 0..n/2 {
            for j in i+1..n/2 {
                ability_start +=
                    abilities[team_start[i]][team_start[j]] 
                        + abilities[team_start[j]][team_start[i]];
                ability_link +=
                    abilities[team_link[i]][team_link[j]] 
                        + abilities[team_link[j]][team_link[i]];
            }
        }
        // 능력치 차이 계산
        let ability_diff =
            max(ability_start, ability_link) - min(ability_start, ability_link);
        *minimum = min(*minimum, ability_diff);
        return;
    }
    // 종료조건: 더 이상 고를 사람이 없는 경우
    if index == n {
        return;
    }
    //pick
    picks[index] = true;
    pick_or_not(n, index + 1, pick_count + 1, picks, abilities, minimum);
    picks[index] = false;
    //or not
    pick_or_not(n, index + 1, pick_count, picks, abilities, minimum);
}