Joonas' Note

Joonas' Note

BOJ 15656 - 치킨 배달 본문

알고리즘/문제 풀이

BOJ 15656 - 치킨 배달

2018. 4. 17. 17:04 joonas

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


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

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

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


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


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


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





    '알고리즘 > 문제 풀이' 카테고리의 다른 글

    BOJ 2225 - 합분해  (0) 2018.04.24
    BOJ 3075 - Astromeeting  (0) 2018.04.18
    BOJ 15685 - 드래곤 커브  (0) 2018.04.17
    BOJ 12755 - 수면 장애  (0) 2018.04.17
    BOJ 2022 - 사다리  (0) 2018.02.08
    Comments