allgoodlife   3달 전

코드는 아래와 같고 예제 test case에 대한 결과는 알맞게 나오는 걸 확인하였습니다.

첫번째 시도에서 일일이 모든 석순과 종유석에 대하여 counting을 해주었고 시간초과가 나서 

이미 질문하신분들의 시간초과에 대한 힌트를 참고하여 풀고자 했습니다.


lower_bound, upper_bound를 가지고 해결하려고 아래와 같이

짰습니다만 여전히 시간초과가 나오는데 어느부분에서 시간을 줄여줄 수 있을까요~

고수님들의 조언부탁드립니다.

dlwodnsdl   3달 전

구간마다 일일히 닿는 종유석의 개수를 구하기 보다는 위에서 부터 n번째 구간에서 부딪히는 종유석의 수는 위에서부터 n+1번째 구간에서 부딪히는 종유석의 수+길이가 n인 종유석의 수인 것을 이용하면 O(n)의 시간만에 해결이 가능하니다.

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