kth   5년 전

일단 dp방법은 생각나지 않아서 우선순위큐로 구현해보자 하는 마음에 구현 했습니다만 시간초과도 아니고 틀렸습니다. 라고 떠서 어떤 부분이 반례인지 알려주실수 있나요?

djm03178   5년 전

어떤 도시에 최고 점수로 도달하기 위해 지나야 하는 도시의 수가 많아서, 이 때까지 도시를 더 적게 지나왔다면 당장의 점수는 적더라도 이후에 다른 도시들을 더 많이 거치면서 많은 점수를 딸 수 있음에도 불구하고 그러지 못하는 경우가 생길 수 있습니다.

아래의 예시를 예로 들면, 1->2, 2->3을 통해서 먹는 20점의 기내식만 보고 달려갔더니, 3->4에 있는 10000점짜리 기내식을 먹기에는 M 제한에 걸려서 5까지 갈 수가 없어 겨우 1점짜리 기내식 하나밖에 더 못 먹고 21점에 만족하게 됩니다. 하지만 처음에 욕심을 참고 1->3으로 5점짜리 기내식을 먹으면, 3->4의 10000점짜리 기내식과 4->5의 100점짜리 기내식을 모두 먹을 수 있어 총 10105점의 기내식을 먹을 수 있습니다.

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