[2017-10-07] The County Fair

링크 : https://www.acmicpc.net/problem/14777

그다지 어려운 문제가 아니었는데 문제 해석이 잘 안 돼서 한참 끙끙댔다. n개의 도시가 있고 첫 도시에서 시작해서 pi시간에 어떤 도시에 있을 수 있으면 그 도시에서 수여하는 상을 받을 수 있고, n개 도시 각각에 대해 움직이는데 걸리는 시간이 주어졌을 때 최대한 받을 수 있는 상 개수를 구하는게 문제다. 처음에 도시 개수 * 최대 시간 으로 모든 도시 왔다갔다하는거 다 계산하는 DP를 생각했는데 이러면 최대 시간 범위가 100만이라 시간 초과가 난다. 좀 더 생각하면 줄일 수 있는데, 각 도시에 대해 그냥 그 도시에서 수여하는 상 받을 지 아닐 지만 고민하면 되고, 이건 어떤 도시에 p[i]보다 일찍 도착한 다음 p[i]까지 기다리면 그 도시에서 수여하는 상 받을 수 있는 거기 때문에 이를 이용해서 간단하게 O(N^2) DP를 짤 수 있다. N 범위가 400이라 충분.