반응형
스타트와 링크
-
BOJ) 스타트와 링크알고리즘/백준 2020. 7. 2. 16:22
스타트와 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 주어진 짝수 인원(4~20)이 축구 경기를 하는데, n/2 : n/2 경기를 해야한다. 이 때, 실력차이가 가장 적게나는 경우를 찾는 문제다. 결국, 모든 경우의 수를 다 파악해야하는 Brute-force 문제였다. n이 20이나 되지만, DFS를 선택했다. 왜냐하면, N=20인 경우, 10 : 10 경기를 하기 때문에, 결론적으로는 2^20까지 가지 않기 때문이다. 중간에 한쪽 팀이 N의 절반이 넘어가는 경우를 가지치기만 해준다면 가능하다고 생각했다. dfs를 통..