kckc0608   7달 전

조금 무식하게 케이스를 분류해서 풀고자 했습니다.

양수만 넣는 케이스, 음수만 넣는 케이스, 양수1개 음수 2개, 양수2개 음수 1개

양수와 음수가 섞이는 경우, 2개가 들어가는 것 중 하나를 고정시키고 나머지 하나를 lower bound 로 찾았습니다.

이때, lower bound 뿐만 아니라, 그 직전 값도 정답의 후보가 될 수 있다고 생각해 추가로 검사하도록 하였습니다.

(사실상 O(N^2) 으로 2개를 고르고 나머지 1개를 이분탐색으로 찾는 것인데, 검색을 통해 이 알고리즘은 시간초과를 받아야 함을 알게되었습니다.)

그런데 pypy3 로 제출했을 때 TLE 가 아니라 WA 를 받는데 이 풀이의 구멍이 어딘지를 모르겠습니다.

혹시 min_diff 의 값을 너무 작게 잡았나 싶어서 늘려보았지만 여전히 틀리는데 왜 TLE가 아니라 WA를  받는 건지 알 수 있을까요?

ai4youej   7달 전

반례입니다

5
1 2 7 -10 5

kckc0608   7달 전

감사합니다! 큰 도움이 되었습니다 :)

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