합승 택시 요금에 대한 문제이다.
문제는 2가지로 풀어볼 수 있을 것 같다.
1번째로는 다익스트라, 2번째로는 플로이드-와샬이 가능하다고 생각했다.
https://ds-jungsoo.tistory.com/7
Shortest Paths(다익스트라 알고리즘 (Dijkstra Algorithm))
이번에는 다익스트라 알고리즘에 대해서 공부를 해보았다. 다익스트라 알고리즘은 단일 시작점으로부터 다른 노드들까지의 최단 경로를 구하는 알고리즘이다. 또한, 음의 가중치를 허용하지
ds-jungsoo.tistory.com
다익스트라에 대해서 공부했기 때문에 다익스트라로 생각해보았다.
Dijkstra를 두번 사용하는 것으로 접근을 하였고,
1번째는 A,B가 같이 가는 구간 (합승 구역)
2번째는 합승 후, 각자 가는 구간
해서 min(answer, 1+2) 답을 구해내는 것이었다.
다익스트라, 벨만, 플로이드 3가지 코딩테스트 문제의 유형은 상당히 비슷했다.
나처럼 코딩머리가 없으면 유투브에서 본 내용인데 대표적인 유형의 코드를 통째로 외워서 시작하면 좋다고 한다. 문제에 비해 코드는 생각보다 짧은 문제들이 많다. 외운 것을 바탕으로, 주어진 문제의 조건에 맞춰서 바꿔나가면서 연습을 하는 방법이다. 익숙해지면 자연스럽게 코드를 구현할 수 있을 것이라고 생각한다. 나도 이 방법을 사용해 볼 계획이다.
'코딩테스트' 카테고리의 다른 글
| 백준 5904 : moo 게임 (0) | 2021.10.25 |
|---|---|
| 백준 2577 : 숫자의 개수 (0) | 2021.10.18 |
| 백준 1260 : DFS와 BFS (0) | 2021.10.17 |
