문제

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

해설

최대 2N개의 집이 있을 때, 치킨집 중 M개를 선택하여 집들과 치킨집들 사이 치킨 거리 가 최소가 되도록 구하는 문제입니다. 치킨 거리 를 구하는 구체적인 방법은 문제에 기술되어 있습니다.

시간복잡도 계산

$2 \leq N \leq 50, 1 \leq M \leq 13$ 에서 치킨집은 최대 13개 이하고, 집은 최대 2N개입니다. $_{13}\mathrm{C}_{k} \leq 1716$ 이므로 최대 uptime은 대략 $1716 \times 2N \times M \leq 10^9$ 로, Brute-force로도 충분히 해결 가능합니다.

구현

입력을 받을 때, 집의 위치와 치킨집의 위치는 따로 vector에 저장해둡니다.

next_permutation을 활용해 치킨집들 중에 M개를 선택합니다. 각 경우에 대하여 도시의 치킨 거리 를 구합니다.

소스 코드

http://boj.kr/f4b17d380737470296f3ee2fca69f1c8

---

참고

• next_permutation을 사용해 조합 구하기
• 이 문제에서 치킨 거리 라고 부르는 용어는 사실 맨해튼 거리입니다.