wjddhfaktmxj   6년 전

푸신 분들을 보니까 대부분 두 엘레베이터가 연결되었는지 여부를 Naive하게 for문을 돌면서 하나하나 체크한 것 같습니다. 이 과정에서 이론상 최대 N번의 for문을 돌아야 하고 총 체크해야하는 엘레베이터 쌍은 M^2개 있으므로 그래프를 만드는데만 O(NM^2)이 걸릴 것 같습니다.

하지만 그런 케이스의 입력을 만드는 것이 쉽지는 않더라고요. 


100000 100

1 2

2 2

1 2

2 2

....

이런 입력을 만들었을때 거의 1초 가까이는 가지만 시간초과를 하지는 않는 것 같습니다.

여기서 조금만 더 입력을 잘만든다면 O(NM^2)으로 그래프를 만든 풀이들을 시간초과나게끔 만들수 있지 않을까요?


chogahui05   6년 전

제가 이걸 잘 안 풀어봐서 모르겠는데요..

대부분 두 엘레베이터가 연결되었는지 여부를 Naive하게 for문을 돌면서 하나하나 체크한 것 같습니다.

이렇게 입력을 주면 몇몇 코드에 대해서 어떻게 동작하나요?

chogahui05   6년 전

아니면 어느 분이 TC 요청하신 이 케이스를 넣던지..

이론적으로.. 이런 류의 문제는 흐음.. 나이브하게 for문을 돌려서 시간초과가 안 날 이유가 하나도 없거든요.

wjddhfaktmxj   6년 전

@chogahui05

답글 감사합니다!


코드를 첨부하자면 아래와 같은 식으로 M^2개의 엘레베이터 쌍에 대해서 둘이 겹치는지 여부를 최대 O(N)짜리 for문을 통해서 체크를 하고 있습니다. 물론 중간에 for문이 N번보다는 조금 돌아가고 겹치는게 나오면 바로 리턴하기는 하지만 이론상으로는 O(M^2N)의 시간복잡도를 가지는 것 같아서요. 그래서 혹시  M^2개의 엘레베이터 쌍에 대해서 저 hasEdge()함수가 대략 N번씩 돌아가는 인풋을 만들수 있지 않을까 생각했습니다. 하지만 N이 조금 커지지 않으면 거의 그런 인풋을 만드는 것이 불가능할 것 같기도 하네요 ㅠㅠ.


 이런 생각을 하게된 이유는 이 문제의 출제 의도가 각 층별로 연결상태를 그래프로 만든 O(N^2)풀이가 아닌 엘레베이터끼리 연결그래프를 만든 O(M^2)풀이인 것 같은데 여기서 엘레베이터끼리 연결된 경우를 O(N)에 체크하는것이 이상해서입니다.


즐거운 성탄절 되세요!

chogahui05   6년 전

맞네요. wj님 말씀대로 테케가 굉장히~ 굉~~~장히 많이 허술하네요.

https://www.acmicpc.net/board/...


이 부분에 대해서는 의견에 올렸습니다.

맞은 분들 중에서 제가 제시한 input을 넣으면 잘못된 답이 나온 경우도 상당히 많이 있었습니다.

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