na982   7달 전

사건번호와 해당사간을 어떤 자동차가 해결할지를 캐싱해 나가면서 문제를 해결했는데, sample은 맞는데 오답이 나오네요;


solve(0, 0, a_car_pos, b_car_pos)

a차가 사건을 해결할 경우 : solve(1, 0, next_pos, b_car_pos) + [a_car_pos ~ next_pos] 까지 거리

b차가 사건을 해결할 경우 : solve(1, 1, a_car, next_pos) + [b_car_pos ~ next_pos] 까지거리


두경우중 최소값을 캐싱하였습니다;

될것같은데;; 잘 안되네요~

na982   7달 전

다른솔루션으로;

각 사건지점 또는 시작 끝 지점 간의 거리를 미리 구해두고,

A 자동차가 다음 사건을 해결하는경우, B 자동차가 다음 사건을 해결하는 경우 둘중 작은경우를 저장하는 방식으로

dp 식을 수정하였는데도 오답이네요..ㅜ

dy0314   3달 전

이러한 방식으로 각 단계마다 path를 저장하는것이 꼭 답을 보장하지 않습니다.

예를 들어 지금 단계에서는 최소값이 2번 차를 부르는 것 일수도 있지만 전체적으로 보았을 때에는 1번차를 부르는 것이 최소값일 수도 있습니다.

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