skan1543   2년 전

제가 생각한 솔루션은..

가장 출발점이 될수있는 선부터 탐색을 시작하여.. 

이 선을 타고 올라갔을때, 타고 내려왔을때.. 각각의 만나서 이어지는 선들을 전부 찾은뒤.. 값을 갱신해주는 형태로 풀었는데요..ㅠㅠ

피곤해서 설명이 횡설수설이네요..

 찾을건 이진탐색으로 찾아주고.. 나름 시간복잡도를 O(N(lgN+x))까지 줄였는데 흑흑 ㅠㅠ

어떻게 해주어야 할까요...ㅎ

arine   2년 전

x, y가 t, d인 것 같은데 범위가 10^8까지 입니다. 시간 복잡도가 O(n(lg n+x))라 하셨으니 약 10^13까지도 돈다는 것인데 이러면 시간초과가 날 수 밖에 없겠죠. (시간제한이 1~2초일 때 보통 10^8정도까지 안전하다고 봅니다.)

이 문제를 풀기 위해 생각해야 하는 것은, n개의 막대기를 왼쪽부터 1,2,3,...,n번 막대기라 했을 때, k번째 막대를 끝으로 해서 만들 수 있는 지그재그 선의 최대 길이를 이미 알고 있다고 가정해봅시다. 그렇다면 k+1,...,n번째 막대에 대해서 이미 알고있는 값을 이용해 최대 길이를 구할 수 있지 않을까요?

여기까지 생각하셨다면 이 문제를 해결하기 위해 써야 하는 몇 가지 트릭이 더 있는데, 모바일로 꾹꾹 눌러적으려니 힘이 드네요...^^;; 마침 이 문제는 제가 연습하면서 정리해 두었던 것이라 링크(http://arine.me/plog/boj8984/)를 남깁니다. 스포일러 수준으로 해법이 적혀 있으니 다 푸신 후나 정 해법이 떠오르지 않을 때 참고하시면 좋을 것 같아요. 

skan1543   2년 전

감사합니다... 그냥 대강 질문을 올려봤는데.. 답변 달아주셔서 감사드리구요 ㅠㅠ

풀이가 문뜩 떠올라 코딩하고 있던 참이었습니다. ㅎㅎ 

바보같이 좌표를 갖고 동적계획을 하면 되는것을.. k번째 선까지 사용한 최대 길이. 를 구하려 하니 TL이 나는거였네요 ㅠㅠ

감사합니당 (_ _)

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