스타트와 링크
-
[Algo Rhythm🕺💃]BOJ 14889 - 스타트와 링크Algo Rhythm🕺💃/BOJ 2021. 6. 18. 23:44
문제 분석 스타트팀을 $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을 사용하여 해결했다. 문제 풀이 ..