[백준] 14889번: 스타트와 링크 - python

문제 출처

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

14889번: 스타트와 링크

 

 

 

---

풀이 및 코드

필자는 해당 문제를 처음 봤을 때는 아무래도 시간초과가 걱정 됐다. 모든 데이터를 살피고 계산까지 하려면 완전 탐색(bfs, dfs)보다는 dp를 이용해 문제를 풀어야 한다고 생각했고 이런 저런 고민을 해보았지만 딱히 떠오르지 않아 완전 탐색(bfs, dfs)으로 접근해 문제를 해결하였다. bfs(deque)와  dfs(재귀) 두가지 방법으로 풀어보았고 그 풀이를 포스팅 하고자 한다.

 

 

 

 BFS(deque)

나눠질 두 팀을 left, right라고 하자. 0번부터 n-1까지 한명씩 돌면서 팀을 배정하고 현재 상황을 dq에 저장하는 방식으로 bfs를 진행하였다. dq에 저장되는 값은 길이가 4인 1차원 배열로 [left팀, right팀, left팀 능력치 합, right팀 능력치 합]으로 저장했다. 특정 팀에 선수가 n/2보다 적을 때에만 선수를 추가해 주었으며 능력치 계산은 새로운 선수가 주어질 때마다 능력치의 합을 생신했다.

 

 

 

 DFS(재귀)

해당 방식은 def dfs(i, left)와 def calculation(i, left)  두 함수를 사용해 구현하였다. dfs 함수는 i번째 선수를 받아 팀을 선택하도록 만들고 만일 두 팀중 한팀이라도 n/2명이 다 채워지면 calculation을 호출한다. calculation함수는 각 선수들을 모아 능력치의 합을 계산해 answer을 업데이트 하는 함수이다.

 

 

 

해당 문제는 삼성 기출 문제로 silver2에 배치되어 있다.