티스토리 뷰
https://www.acmicpc.net/problem/4485
4485번: 녹색 옷 입은 애가 젤다지?
젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주
www.acmicpc.net
다익스트라 알고리즘을 이용한 문제.
왼쪽 상단에서 우측 상단까지 이동했을때 최소로 잃을수 있는 코인의 수를 구해야 한다.
이차원 배열에 해당 지점까지 이동했을때 최소로 잃을수 있는 코인의 수를 저장한다.
해당 배열은 다익스트라 알고리즘에서 처럼 최초에 최대값으로 저장해야한다.
왼쪽 상단 부터 bfs 알고리즘으로 이동한다.
현재 지점까지 이동했을때 최소로 잃을수 있는 코인의 수 + 다음 지점에서 잃어야 하는 코인의수가 최소가 되도록 갱신해 나간다.
'PS' 카테고리의 다른 글
| 백준 20055. 컨베이어 벨트 위의 로봇 (0) | 2022.05.19 |
|---|---|
| 백준 1238. 파티 (0) | 2022.05.19 |
| 백준 1261. 알고 스팟 (0) | 2022.05.18 |
| 백준 1916. 최소비용 구하기 (0) | 2022.05.18 |
| 백준 17406. 배열 돌리기 (0) | 2022.05.18 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Stack
- graph
- Spring
- floyd warshall
- Brute Force
- Unity
- dfs
- CSS
- C
- 이분탐색
- binary search
- 자료구조
- two pointer
- back tracking
- Dijkstra
- DP
- Kruskal
- db
- BFS
- MVC
- recursion
- priority queue
- Python
- 재귀
- greedy
- Implementation
- permutation
- C++
- Tree
- 조합
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 |
글 보관함