minjae200   2년 전

나름대로 줄여보았는데도 시간초과가 나옵니다. 간단한 문제라 생각했는데 시간을 줄이는 방법이 생각나지 않습니다....

아이디어좀 주실분 계신가요

minjae200   2년 전

어떤 TC에 대해서 무한루프가 도는걸까요 아니면...스위치문에서 case 1에서 오래걸리는건가요 ㅠㅠ

jh05013   2년 전

최악의 경우 이 코드의 시간복잡도는 얼마일까요?

참고로 이 문제는 UCPC 2018 예선에서 가장 어려운 문제였습니다.

minjae200   2년 전

@jh05013

음ㅠㅠㅠㅠㅠ 시간초과뜰걸 예상은 했지만...잘모르겟습니다 ㅠㅠ

jh05013   2년 전

그래도 풀고자 하신다면, (p, q) pair를 만드는 것은 맞게 접근하셨습니다. 그런데 이 q개의 쓰레기를 road에 하나하나 집어넣으려고 하면 비효율적인 코드가 됩니다. 소각로 전체를 구현하지 말고 temp만으로 L번 쓰레기와 R번 쓰레기를 찾는 방법을 생각해 보세요.

jh05013   2년 전

저 코드의 문제점은 1번 쿼리의 시간복잡도가 O(R-L)이라는 것입니다. 그래서 전체 코드가 O(Q(R-L))이 되고, Q와 R-L의 최대값을 넣어 보면 시간초과가 나옵니다.

minjae200   2년 전

@jh05013 아!! 감사합니다. 알것같습니다. 감사합니다!!!

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