2586번 - 소방차
DP 점화식은 맞게 세운 것 같은데(작은 범위에서 답이 나옵니다),
여기서 더 생각을 못하겠습니다.
당연히 p<=100000, f<=100000인 범위에서 이중 for 문의 범위를 관리해준다고 해도 최악의 경우 O(n^2)이기 때문에 시간 초과로 결론나는 것은 파악하였으나,
시간복잡도를 어떻게 줄일 수 있을지 모르겠습니다. DP 최적화 테크닉을 찾아봐야 하는 걸까요?
감사합니다. 시도해보겠습니다!
댓글을 작성하려면 로그인해야 합니다.
dyepeyyt 8달 전
DP 점화식은 맞게 세운 것 같은데(작은 범위에서 답이 나옵니다),
여기서 더 생각을 못하겠습니다.
당연히 p<=100000, f<=100000인 범위에서 이중 for 문의 범위를 관리해준다고 해도 최악의 경우 O(n^2)이기 때문에 시간 초과로 결론나는 것은 파악하였으나,
시간복잡도를 어떻게 줄일 수 있을지 모르겠습니다. DP 최적화 테크닉을 찾아봐야 하는 걸까요?