artichoke42   2년 전

입력의 각 줄의 첫 번째 정수, 즉 경로에 포함된 정점의 개수에 제한이 없다면, 최대 N^2개(약 4억개)까지 가능하며, 이러한 입력이 존재하는 경우 입력만으로 시간초과가 발생하는 경우가 생길 수 있을 것 같습니다.

이에 따라 경로에 포함된 정점의 개수에도 제한이 필요할 것 같습니다.

jh05013   2년 전

선인장이라는 조건에 의해 간선 개수가 O(N)으로 제한됩니다.

artichoke42   2년 전

선인장이 아닌 경우 0을 출력하라는 지문으로 보아 O(N^2)이 여전히 가능해 보입니다.

jh05013   2년 전

아 선인장이 주어진다고 해서 속았네요... 이 문장도 수정해야 될 것 같습니다. 따로 글을 올리겠습니다.

startlink   2년 전

수정했습니다.

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