mypark3424   9달 전

몇일동안 고민해봐도 시간초과를 줄일 수 있는 방법이 떠오르지 않습니다.


도와주시면 감사드리겠습니다!!

yukariko   9달 전

좌표를 정렬된 상태로 생각한다면, dp 정의를 아래와 같이 생각해 볼 수 있습니다.

dp[left][right][pos] = 내가 [left, right] 범위의 김치를 모두 배달했고, pos 위치(left or right 중 한 곳)에 있을때, 나머지 김치를 배달할 때의 쉰 정도의 최소값

이때의 공간 복잡도는 O(N^2) 입니다.

남은것은 이제 left-1 과 right + 1 둘 중 한곳으로만 보내준다면, 재귀 함수안에 반복없이 문제를 해결할 수 있습니다.

이 때의 시간복잡도는 상태공간 O(N^2)과 거리 계산 O(N)으로 O(N^3) 이 됩니다.

여기서 거리 계산을 부분합을 통해 미리 구해준다면, 시간복잡도를 O(N^2)로 줄일 수 있습니다.


mypark3424   8달 전

yukariko님께서 말씀하신대로 코드를 짜봤는데 아직도 안되서 질문드립니다!!

부분합을 통해서 거리계산까지 미리하였고 이전pos와 현재 pos를 활용하여 ret값을 업데이트 해가는 식으로 코드를 짰습니다.

아직도 시간초과가 나서 뭐가 잘못됬는지 도저히 찾지를 못하고있습니다.

도와주셨으면 합니다!! 감사합니다.

bluespace   8달 전

cheer up

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