[Algo Rhythm🕺💃]BOJ 14889 - 스타트와 링크

문제 분석

스타트팀을 $T_{start}$, 링크팀을 $T_{link}$ 그리고 두 팀의 능력치를 각각 $S_{start}, S_{link}$라고 하자. 이때 각 팀에 속하는 사람들의 수는 두 팀 모두 축구를 하는 $N\ (4 \le N \le 20)$명의 절반인 $N / 2$ 명이다.

문제에서 요구하는 $min(|S_{start} - S_{link}|)$를 구하기 위한 가장 직관적인 방법은 $(T_{start}, T_{link})$의 모든 조합을 구한 뒤 각 조합의 $|S_{start} - S_{link}|$을 구하고 그 중 최소값을 찾는 것이다.

모든 조합을 구해야 하는 문제들은 주로 'backtracking'을 사용한다. 이 문제도 마찬가지로 backtracking을 사용하여 해결했다.

 

문제 풀이

축구를 하는 사람들마다 고유의 id가 있고 그것들을 각각 1, 2, ... , N이라고 하자. 그리고 각 id를 하나의 vertex라고 생각해보자.

그렇다면 우리는 $(T_{start}, T_{link})$의 모든 조합을 구하는 문제가 결국 (선택한 N / 2개의 vertex, 선택하지 않은 N / 2개의 vertex)의 모든 조합을 구하는 문제와 같다는 사실을 알 수 있다. vetex들을 선택할 때는 이미 선택되지 않은 vertex들만 선택하고 이때 쓰이는 점화식은 다음과 같다.

 

$f(id, n_{member}, N) = \begin{cases}calc\ |S_{start} - S_{link}|\ and\ compare&if\ n_{member} == N / 2&(base\ case)\\f(id + 1, n_{member} + 1, N)&else\ if\ vertex_{id + 1}\ is\ not\ visited&(recursive\ case)\end{cases}​$

 

이때 주의할 점은 모든 조합을 구하기 위해 1부터 N까지 backtracking할 필요가 없다는 것이다. 왜냐하면 N / 2개의 vertex만 선택하면 나머지 N / 2개의 vertex들은 자동으로 결정되기 때문이다. 따라서 N / 2개의 vertex만 backtracking하여 문제를 해결하도록 구현해야 한다.

예를 들어 4개의 vertex 중 2개를 선택하면 가능한 조합은 $(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)$이렇게 6개이다. 하지만 $(1, 2)$ 선택시 선택되지 않는 vertex들은 자연스럽게 $(3, 4)$가 되는 것을 알 수 있다.

 

복잡도 분석

n명의 사람들이 축구를 한다고 할 때 복잡도는 아래와 같다.

 

시간 복잡도 : $O(n!)$

- recursive call을 $i$번 했을 때 각 recursive call마다 선택할 수 있는 id 즉, vertex가 $N - i$개 존재하기 때문이다.

 

공간 복잡도 : $O(n^2)$

- 같은 팀일때 능력치를 기록한 2차원 배열 : $O(n^2)$

- n개의 vertex에 대한 visit 여부를 기록하는 배열 : $O(n)$

- $T_{start}, T_{link}$에 대한 정보를 가지는 vertor : $O(n)$

 

코드

 

문제 출처 및 원본 문서

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

14889번: 스타트와 링크

https://www.notion.so/BOJ-14889-cb96bb89dce24aa88b7b955bc050c074

BOJ 14889 - 스타트와 링크