phsindong   6달 전

2466번 문제인데 시간 초과가 나서 방법이 맞는것인지 궁금합니다.

사용한 방법은 이분법을 사용하였고 이분법에서 매번 반복의 true, false를 체크할때 dp를 사용하였습니다.

코드의 solve함수가 너비가 정해졌을때(int val)  최소 높이를 구하는 dp함수입니다.

최대개수가 10만이어서 dp에서도 시간이 상당히 걸리는것 같은데요

dp보다 더 빠른방법이 있는건지 아니면 이분법 +  dp 인 전체적인 풀이방법이 바뀌어야하는것인지 궁금하네요


pl0892029   6달 전

으... 굉장히 오랜 시간동안 풀었던 문제네요.

먼저, 이 문제의 데이터가 "굉장히 약한 편" 입니다. 그래서서 풀이가 2개 존재하게 됩니다.


1) Fenwick-tree를 이용해서 DP를 O(NlogN)으로 줄이기

    이 경우의 시간복잡도는 O(N(logN)^2) 형태가 나오게 되서 데이터의 형태에 종속되지 않고 통과가 가능하겠지요.

2) 책장의 높이에 영향을 주지 않는 후보들을 추려내기 - monotonous stack

    이 경우의 시간복잡도는 O(N^2) 입니다. 근데 이게 정말 빨라요. 이런 경우를 허용한건지, 데이터가 부실한건지(...)


저는 2번 방식으로 풀었었는데, monotonous stack을 먼저 찾아보시고, 책장 문제를 다시 읽어서 후보군을 추리는 방법을 고민해보세요.

그래도 감이 잘 안오신다면, 제 블로그 글을 보시면(...) 되겠습니다.

http://blog.naver.com/gg7308/memo/70143863303

pl0892029   6달 전

위의 2) 풀이의 시간복잡도는 O(N^2logN)입니다. 적고나니 깨달았는데, 수정방법이 없네요.

koosaga   6달 전

윗분이 정말 잘 적어주셨는데 저의 경우에는 stack 풀이를 최적화해서 nlg^2n에 풀었습니다. http://www.usaco.org/current/data/sol_bookshelf_go... 도움이 될거같네요

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