11067번 - 모노톤길
왜 시간초과가 나는지 이해를 할 수가 없습니다.
힙2개에다가 넣고 빼고만 하는데 왜 시간초과가 날까요? ㅠ
10만개 넣고 빼는거 해봐야 nlogn이니까 170만정도... 2개니까 340만...
충분히 돌아갈거 같은데 ㅠㅠ?
푸는 방식은 힙 2개를 만들어서 하나는 y 내림차순으로, 다른 하나는 y를 오름차순으로 갖도록 해서..
두개다 뽑아낸다음에 y 값을 서로 비교하거나 이전 x값(코드에서는 px라고 표현)을 비교해서 방향을 결정하도록 했습니다.
코드도 간단해서 보시면 금방 아실 수 있으실거에요...
4% 채점중에 시간초과가 납니다.
도와주세요 !! ㅠ
bfs 로 풀지말고 dp로 풀어보시는게...
길이 하나밖에 없는데 bfs라고 하기엔 그렇지 않나요? ㅎ 저 코드도 bfs는 아닌데.. ㅎ
아무튼 전 이걸 dp로 어떻게 푸는지 감도 안잡히긴 하는데;;
그냥 sorting한번 써서 해결했습니다 ㅎ
넵.. 도움이 안되서 죄송해용 ㅠㅠ
@dtc03012
ㄷㄷㄷ 그런 말은 아니었어요 ㅠㅠ
혹시 dp로 푸셨다면 점화식좀 알 수 있을까요??
음.. 진짜 죄송한데 제가 푼게 아니라
대회 때 제 친구가 저 문제를 dp로 풀었었거든요... 그게 기억나서 말해본거에요
다른분들 코드 한번 봐볼게요 ㅎ;
답변은 언제나 감사합니다! ^^;;
댓글을 작성하려면 로그인해야 합니다.
plzrun 8년 전
왜 시간초과가 나는지 이해를 할 수가 없습니다.
힙2개에다가 넣고 빼고만 하는데 왜 시간초과가 날까요? ㅠ
10만개 넣고 빼는거 해봐야 nlogn이니까 170만정도... 2개니까 340만...
충분히 돌아갈거 같은데 ㅠㅠ?
푸는 방식은 힙 2개를 만들어서 하나는 y 내림차순으로, 다른 하나는 y를 오름차순으로 갖도록 해서..
두개다 뽑아낸다음에 y 값을 서로 비교하거나 이전 x값(코드에서는 px라고 표현)을 비교해서 방향을 결정하도록 했습니다.
코드도 간단해서 보시면 금방 아실 수 있으실거에요...
4% 채점중에 시간초과가 납니다.
도와주세요 !! ㅠ