합승 택시 요금1 [카카오 기출] Swift - 합승 택시 요금 합승 택시 요금 다익스트라 🍎 지문 해석 무지는 택시비를 아끼고 싶다. 어피치와 택시를 같이 타고 일정 지점까지 같이 가고 거기서 따로 택시를 타고 집에 갔을 때와 처음부터 각자 따로 갔을 때를 비교해서 더 적은 금액이 무엇인지 구하면 된다. V = 200 E = (200 * 199) / 2 시간복잡도 Elog(V) -> 200log200 하나의 정점에서 다른 모든 정점까지 최소 요금을 구하는 경우 -> 200log200 🍎 문제 접근 음의 가중치가 없는 간선에서 최단거리 -> 최소힙 기반의 우선순위 큐를 통한 다익스트라 알고리즘 두가지를 구해야 한다. 시작 지점 S에서 A와 B까지 각자 택시를 타고 갔을때, S -> A, S -> B 이 부분은 S에서 모든 정점까지의 최소 요금을 구한 후 이미 구해진 .. 2023. 8. 25. 이전 1 다음