백준 (206) 썸네일형 리스트형 백준 - 1219 : 오민식의 고민 https://www.acmicpc.net/problem/1219 문제의 맥락을 보면 최단 경로 알고리즘을 사용해야 되는 것으로 보인다. 출력 문단을 살펴보면 3가지 케이스를 구분할 것이 요구됨을 알 수 있다. 도착이 가능할 경우 소지금의 최댓값 도달 자체가 불가능할 경우 "gg" 출력 도착했을 때 돈이 무한으로 발산한다면 "Gee" 출력 이 케이스들을 개별적으로 생각해보자. 첫 번째는 이익이 최대로 되는 경로를 찾으면 된다. 두 번째는 도달 가능성을 판단하면 된다. 세 번째가 생각하기 어려울 수 있는데, 경로를 탐색하던 중 음수 사이클(문제에서는 이익 사이클)로 진입했지만 도달할 수 있는 경로가 존재한다면 돈을 무한정 벌게 되는 것이므로 사이클 존재 여부와 도달 가능성을 판단하면 된다. 즉 세가지를 종.. 이전 1 ··· 39 40 41 42 다음