반응형
4485
-
BOJ) 녹색 옷 입은 애가 젤다지? (4485 번)알고리즘/백준 2021. 1. 19. 00:33
녹색 옷 입은 애가 젤다지? 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라를 알고, 적절하게 이용할 줄 아는가?를 물어보는 문제였다. 좌측 상단에서 우측 하단으로 이동하면서 돈을 가장 적게 뺏겨야하는 문제다. 처음에는 dp로 간단하게 풀 수 있겠다고 생각하고 코드를 작성했지만, 불규칙적으로 왔다갔다하는 경우가 있어서 다익스트라를 추가해줬다. 출발 지점을 우선순위 큐에 담아두고, 상하좌우를 돌면서 돈을 가장 적게 뺏기는 경우들을 저장하면서 큐에 넣어주었다. 이동하면서, 가장 적게 ..