lus6   3년 전

뒤늦게 알고리즘공부에 열심힌데 틀린경우의수를 못찾겠네요.

예제는 당연히 맞고 

5 17

2 6

50001 99999 까지 넣어봤는데 이중에서 틀린건 없는거같아요.

소스코드 봐주시면 감사하겠습니다.


그리고 알고리즘 틀렸는지여부를 간단하게라고 점검해볼수잇는방법 있을까요?

시험에선 제출하는것만 있고 맞았는지 틀렸는지여부를 안가르쳐주는경우가 많아서 제출했다해도 틀린경우가 많네요.

zlzmsrhak   3년 전

시작 지점과 끝 지점이 같은 경우가 반례인 것 같습니다.

lus6   3년 전

허 그렇군요.... 한번에 맞기가 참 힘드네요 ㅜㅜ

감사합니다.

zlzmsrhak   3년 전

꽤 중요한 질문 하나를 빼먹어서 아래쪽 질문의 답글을 달아보면,

답이 나오지 않을 것 같아보이는 작은 예제를 손으로 만들어서 확인해보거나,

O(N)으로 풀어야 하는 문제를 O(N^2)이나 O(2^N)처럼 안좋은 방식으로 푼 뒤 랜덤한 데이터에 대해 확인을 해 보는 방법이 있습니다.

맞는 답인지 확인하는 것이 어렵지 않는 경우에 대해서는 랜덤하게 큰 데이터를 생성한 뒤, 답을 검증하는 방법도 있습니다.

epikem   1년 전

허.. 20번을 틀리던 걸 이거 보고 n k 4 4 넣었더니 2가 나와서 이것만 고쳤더니 바로 맞아버리네요..

epikem   1년 전

밑에처럼 이전까지 최적이라면 두배 한 다음 +-1의 위치만 체크해주면 되지 않을까 해서 해봤는데 검증 코드까지 써봐도 틀리다고 안나오는데 계속 틀려서 왜그런가 했더니 ans[t] 업데이트 할 때에도 주석처럼 검증을 해야되는거였네요

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