yyyy7089   1년 전

일단 문제에서 DAG라는 언급이 없지만, DAG가 아니면 문제 상태가 정의되지 않으므로 DAG를 이룬다고 가정하겠습니다.

중복 간선이 존재하지 않는다는 말이 없지만, 존재할 경우 어떻게 해야 하는지에 대한 언급이 없으므로 중복 간선도 없다고 가정하겠습니다.

먼저 P의 범위가 없으므로 완전 그래프를 가정할 수 있습니다. (완전 그래프에서 방향을 적절히 지정하여 DAG를 만들 수 있음이 자명합니다.) 따라서 간선은 최대 M(M-1)/2 개 이고, M이 최대 1 000이므로 간선은 최대 499 500 개 입니다. 테스트 케이스가 1 000 개이고 각 테스트케이스마다 P = 499 500 인 경우, 입력받아야 하는 수의 개수만 999 003 001 개입니다. 이것을 1초 안에 입출력하는 것은 mmap 등으로 이론적으로 가능합니다만 입출력에만 400ms 정도를 쓰게 됩니다. (수 5 000 000 개를 입력받아야 하는 11921번 문제의 가장 빠른 풀이가 20ms 내외입니다.) 이후 연산도 총합 O(TN^2)이며, 이러한 연산을 여러 번 수행해야 합니다.

따라서 조건에 따라 이 문제를 풀기 위해서는 최소 50억 번 정도의 연산을 1초 안에 해야 하는 것으로 보이는데, 이 경우 당연히 풀 수 없는 문제가 됩니다.

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