으... 굉장히 오랜 시간동안 풀었던 문제네요.
먼저, 이 문제의 데이터가 "굉장히 약한 편" 입니다. 그래서서 풀이가 2개 존재하게 됩니다.
1) Fenwick-tree를 이용해서 DP를 O(NlogN)으로 줄이기
이 경우의 시간복잡도는 O(N(logN)^2) 형태가 나오게 되서 데이터의 형태에 종속되지 않고 통과가 가능하겠지요.
2) 책장의 높이에 영향을 주지 않는 후보들을 추려내기 - monotonous stack
이 경우의 시간복잡도는 O(N^2) 입니다. 근데 이게 정말 빨라요. 이런 경우를 허용한건지, 데이터가 부실한건지(...)
저는 2번 방식으로 풀었었는데, monotonous stack을 먼저 찾아보시고, 책장 문제를 다시 읽어서 후보군을 추리는 방법을 고민해보세요.
그래도 감이 잘 안오신다면, 제 블로그 글을 보시면(...) 되겠습니다.
phsindong 7년 전
2466번 문제인데 시간 초과가 나서 방법이 맞는것인지 궁금합니다.
사용한 방법은 이분법을 사용하였고 이분법에서 매번 반복의 true, false를 체크할때 dp를 사용하였습니다.
코드의 solve함수가 너비가 정해졌을때(int val) 최소 높이를 구하는 dp함수입니다.
최대개수가 10만이어서 dp에서도 시간이 상당히 걸리는것 같은데요
dp보다 더 빠른방법이 있는건지 아니면 이분법 + dp 인 전체적인 풀이방법이 바뀌어야하는것인지 궁금하네요