본문 바로가기
Algorithm/Programmers

[PRGRMS]72413번: 합승 택시 요금

by BAYABA 2022. 4. 12.

문제: https://programmers.co.kr/learn/courses/30/lessons/72413


플로이드 문제입니다.

 

최저 택시 요금 후보로 갈 수 있는 경로는 크게 4가지입니다.

 

1. A를 경유해서 가는 경우: S => A => B

2. B를 경유해서 가는 경우: S => B => A

3. 각 각 택시를 타는 경우: S=> A + S => B

4. S와 A, B 사이에 임의의 경유지 i를 두는 경우(첫 번째 테스트 케이스): S => i + i => A + i => B

 

플로이드로 모든 경로쌍을 구한 뒤에 위 4가지 경우를 계산하여 최소값을 리턴하면 됩니다.


코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%ED%95%A9%EC%8A%B9%20%ED%83%9D%EC%8B%9C%20%EC%9A%94%EA%B8%88.java

'Algorithm > Programmers' 카테고리의 다른 글

[PRGRMS]12946번: 하노이의 탑  (0) 2022.03.23
[PRGRMS]43238번: 입국심사  (0) 2022.03.23
[PRGRMS]42839번: 소수 찾기  (0) 2022.03.23
[PRGRMS]92343번: 양과 늑대  (0) 2022.03.23
[PRGRMS]92341번: 주차 요금 계산  (0) 2022.03.17