전체 글 (277) 썸네일형 리스트형 백준 10217 - KCM Travel https://www.acmicpc.net/problem/10217 시간제한이 10초라는 점과 어떤 도시로 가는 최소 시간을 구해야 하는 최단경로에 'M원 이하를 사용해야 한다'라는 제약 조건이 붙어있다. 인천에서 LA로 가는 최단 경로만 구해야 되므로 여기에 가장 특화된 다익스트라 알고리즘 사용을 최우선적으로 고려할 수 있다. 다만, 'M원 이하 사용'의 제약 조건으로 인해 DP가 가미된다는 걸 알 수 있는데 문제는 어떤 것을 메모이제이션 해야 하는가이다. DP 배열의 구성을 생각하기 위해 주어진 정보를 정리하면 출발하는 인천의 번호는 무조건 1이다. LA의 번호는 무조건 N(도시의 개수)이다. 시작과 도착이 고정되어 있으므로 다음 1차원 배열을 생각해볼 수 있다. DP[x] == 1에서 x까지의 최단.. 백준 - 1219 : 오민식의 고민 https://www.acmicpc.net/problem/1219 문제의 맥락을 보면 최단 경로 알고리즘을 사용해야 되는 것으로 보인다. 출력 문단을 살펴보면 3가지 케이스를 구분할 것이 요구됨을 알 수 있다. 도착이 가능할 경우 소지금의 최댓값 도달 자체가 불가능할 경우 "gg" 출력 도착했을 때 돈이 무한으로 발산한다면 "Gee" 출력 이 케이스들을 개별적으로 생각해보자. 첫 번째는 이익이 최대로 되는 경로를 찾으면 된다. 두 번째는 도달 가능성을 판단하면 된다. 세 번째가 생각하기 어려울 수 있는데, 경로를 탐색하던 중 음수 사이클(문제에서는 이익 사이클)로 진입했지만 도달할 수 있는 경로가 존재한다면 돈을 무한정 벌게 되는 것이므로 사이클 존재 여부와 도달 가능성을 판단하면 된다. 즉 세가지를 종.. 이전 1 ··· 53 54 55 56 다음
