kalmiaa   4달 전

안녕하세요.

가장 기본적인 dp로는 당연히 N^2으로 쉽게 결과값을 낼 수 있는 문제이나,

인풋 크기로 보았을때 N^2으로는 제한시간을 맞출 수 없다고 생각하여, 여러가지 다양한 방법을 생각하였습니다만,

좋은 방법이 떠오르지 않아 그냥 N^2으로 때렸더니 답이 나왔습니다.


로컬에서 인풋 10000개 때리면 제 코드는 3초정도 나옵니다.

최적화를 통해 오버헤드를 약간 줄일 수는 있겠지만, 근본적인 솔루션은 아닌것 같습니다.


혹시 이 문제를 NlgN 으로 풀 수 있는 방법이 있을까요?


crasy111   4달 전

for i=1~N

  for j=1~i

까지 돌았기때문에, 1~N까지의합, 즉 거의 N^2/2의 시간이 걸리죠. 그러므로 시간안에 나오는게 맞습니다.

또한, 궁금하시다면 다른 분들 소스를 참고해보세요. 제가 본 바로는, NlogN으로 푸신분은 일단 못찾았습니다.

koosaga   4달 전

1만이면 어지간해선 n^2 빠르게 나옵니다. 완전 느리게 짠게 아니면.. 그리고 로컬은 보통 느려요.


n^2보다 빠른 풀이가 옛날에 궁금해서 코포 분들에게 물어본게 있는데.. http://codeforces.com/blog/entry/43729

kalmiaa   4달 전

crazy111님

일단 다른분들 소스는 봤구요.

뭐.. 저도 약간의 오버헤드는 있지만, 거의 비슷하게 풀었습니다.


쿠사가님 코드포쓰 링크 감사합니다


제가 100% 이해하려면 시간이 걸리겠지만,

어쨋든 Full N^2이 아니고, overap 된 부분은 건너뛰고 loop를 타기때문에, naive한 N^2에 비해 속도가 빠르다는거 같구요.

세그먼트트리를 활용해서 가능할것 같다는 아이디어도 보이는것 같네요.





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