plzrun   8년 전

왜 시간초과가 나는지 이해를 할 수가 없습니다.

힙2개에다가 넣고 빼고만 하는데 왜 시간초과가 날까요? ㅠ

10만개 넣고 빼는거 해봐야 nlogn이니까 170만정도... 2개니까 340만...

충분히 돌아갈거 같은데 ㅠㅠ?


푸는 방식은 힙 2개를 만들어서 하나는 y 내림차순으로, 다른 하나는 y를 오름차순으로 갖도록 해서..

두개다 뽑아낸다음에 y 값을 서로 비교하거나 이전 x값(코드에서는 px라고 표현)을 비교해서 방향을 결정하도록 했습니다.

코드도 간단해서 보시면 금방 아실 수 있으실거에요...


4% 채점중에 시간초과가 납니다.

도와주세요 !! ㅠ

dtc03012   7년 전

bfs 로 풀지말고 dp로 풀어보시는게...

plzrun   7년 전

길이 하나밖에 없는데 bfs라고 하기엔 그렇지 않나요? ㅎ 저 코드도 bfs는 아닌데.. ㅎ

아무튼 전 이걸 dp로 어떻게 푸는지 감도 안잡히긴 하는데;;

그냥 sorting한번 써서 해결했습니다 ㅎ

dtc03012   7년 전

넵.. 도움이 안되서 죄송해용 ㅠㅠ

plzrun   7년 전

@dtc03012

ㄷㄷㄷ 그런 말은 아니었어요 ㅠㅠ

혹시 dp로 푸셨다면 점화식좀 알 수 있을까요??

dtc03012   7년 전

음.. 진짜 죄송한데 제가 푼게 아니라

대회 때 제 친구가 저 문제를 dp로 풀었었거든요... 그게 기억나서 말해본거에요

plzrun   7년 전

다른분들 코드 한번 봐볼게요 ㅎ;

답변은 언제나 감사합니다! ^^;;

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