안녕하세요,
재재입니다.
boj 18316 Time is mooney 문제에 대한 솔루션입니다.
BOJ 18316 Time is mooney
(1) 설명
출처: https://www.acmicpc.net/problem/18316
(1000이하) N개의 도시와, (2000이하) M 개의 (단방향) 간선이 주어집니다.
1번 도시에서 출발해서 1번 도시에서 끝나야 하고,
각 도시를 움직이면서 각 도시의 가중치를 더할 수 있습니다.
이때, 현재 T곳을 방문했다면 점수는 다음과 같습니다.
$ cost_{m_1} + cost_{m_2}+…+cost_{m_t} – CT^2 $
이제, 얻을 수 있는 최대 점수를 구해주면 됩니다.
(2) 풀이 도출
직감적으로,
방문 할 수 있는 도시의 갯수에는 제한이 있다는 생각이 들었습니다.
문제에서는 사이클이 존재 할 수 있으나,
방문한 도시 갯수의 제곱 * 상수만큼 빠진다는 사실을 이용해야 합니다.
시간에 따라 방문하는 영역은 점차 넓어질 거고,
bellman ford 알고리즘과 비슷한 느낌으로 특정 시간에 도시에 도착했을 때,
최적의 가중치를 구할 수 있다면 이 문제를 쉽게 풀 수 있을 것 같습니다.
적당히 큰 페널티 부터는, 더이상 방문하지 않는게 이득이기 때문에
적당한 수치를 N의 2배 정도로 잡아보고 구현해도,
아래의 시간복잡도가 됩니다.
$ O(2N*(N+E)) $
넉넉히 2초 안에 해결 할 수 있습니다.
(3) 정답 코드
BOJ 18316 Time is Mooney