dyepeyyt   8달 전

DP 점화식은 맞게 세운 것 같은데(작은 범위에서 답이 나옵니다), 

여기서 더 생각을 못하겠습니다.

당연히 p<=100000, f<=100000인 범위에서 이중 for 문의 범위를 관리해준다고 해도 최악의 경우 O(n^2)이기 때문에 시간 초과로 결론나는 것은 파악하였으나,

시간복잡도를 어떻게 줄일 수 있을지 모르겠습니다. DP 최적화 테크닉을 찾아봐야 하는 걸까요?

zenith82114   8달 전

제가 아는 풀이로 그리디 기반의 풀이와 slope trick을 쓰는 풀이가 있는데, 그 중 후자가 지금 시도하신 접근과 더 가깝습니다.

dyepeyyt   8달 전

감사합니다. 시도해보겠습니다!

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