Rose   1년 전

제가 생각한 알고리즘은 BFS+DP로 n도시로 가는 최대 기내식 점수를 구하는 알고리즘입니다.

d[i][j]=i도시까지 여행하는데 출발점과 자기를 합쳐서 j개의 도시를 거처 온 최대 기내식 만족도

  1. 큐에 1번정점부터 넣어줍니다.
  2. 자기보다 큰 정점으로 가는 현재 최댓값이 현재 점수+ 현재정점에서 그 정점으로 가는 값 보다 작다면 갱신해줍니다.
  3. 마지막에 Max(d[n][1~m])을 구해줍니다

혹시 제 알고리즘이 고려 못한 점이 있거나 시간초과를 야기할만한것이 있다면 조언 부탁드리겠습니다. 

댓글을 작성하려면 로그인해야 합니다.