shjgkwo   1년 전

사실 제 소스에서 나온 예외지만...

USACO 에서 비슷한 문제를 풀다가

제 방법으로 했을때의 예외를 발견했습니다.

1 50000

2 50001

3 50002

.

.

.

49997 99996

49998 100000

100000 100006

100006 100008

.

.

.

200000 1


이런 데이터 인데요

제가 쓴 방법은 트리를 만들어 말단부터 올라가는 방법입니다.

그런데 문제가 뭐냐하면 위에 데이터를 넣으며 말단이 약 50000개가 있고. 그 말단이 모두 한개의 노드에 연결되어 있으며

그리고 그 한개의 노드부터 사향트리의 모습을 띄고있어서, 50000을 50000번 도는, 즉

O(N^2) 시간이 걸리게 됩니다. 말단부터 찾아가면 말이죠..

Root 노드부터 DFS를 돌리면 O(N) 인데 말이죠..

즉, 이런 실수를 한 사람을 걸러내기 위한 데이터가 필요하다고 생각됩니다.

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