BOJ 15656 - 치킨 배달

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

문제 설명 마지막 줄에 다 요약되어있다. 도시에 있는 치킨집 중에서 최대 \(m\)개를 골라야한다.

문제 조건에서 치킨집의 개수는 최대 13개이고, 도시에 있는 치킨집 \(k\)개 중에 \(m\)개를 고르는 경우의 수는 $$C(k, m) = \frac{k!}{m!(k-m)!}$$

숫자가 작아서 많아봐야 1500개가 좀 안되므로 치킨집을 선택하는 모든 경우의 수를 시도해 볼만 하다.

정해진 \(m\)개의 치킨집마다 모든 사람들의 집에 도달하는 최소 거리를 사람이 사는 집 기준으로 저장해둔다. 즉, 어떤 조합에 대해 \(j\)번 집은 가장 가까운 치킨집과의 거리를 저장하고 있다.

매 조합마다 모든 거리를 구하면 오버헤드가 심하므로 미리 모든 치킨집과 집의 거리를 구해놓아야한다.

조합마다 BFS로 시도했지만 생각해보니 시간초과가 당연했다. 조합을 볼 필요 없이 그리디하게 구할 수 있을까 여러 삽질을 했는데 천천히 구현해보니 간단한 문제였다...