dnjsgudtjr11   1년 전

안녕하세요

에디토리얼에서는 이분탐색으로 연료량을 고정하고 dp로 방문 가능 여부만 확인 하는 풀이를 봤는데,

저는 1차원 dp로 dp[i]를 해당 정점에 방문했을 때 사용했던 최대 연료량, 현재 연료량으로 정의하고

현재 사용 연료량 + 다음 정점까지의 거리, 최대 사용 연료량 중 더 큰 값으로 다음 dp를 갱신했는데

이 풀이는 안되는걸까요??

doju   1년 전

먼저 52~53번째 줄에 여러 오타가 있어 보입니다.

이런 문제에서 작성하신 것과 같은 단순 DP가 동작하지 않는 이유는, 지금까지의 고점(.first)은 높지만 현재 사용 연료량(.second)이 낮은 경우와 지금까지의 고점은 낮지만 현재 사용 연료량이 높은 경우 중 후자가 반드시 더 좋다고 말할 수 없기 때문입니다. 후자의 경우 당장의 고점은 낮지만 현재 사용 연료량이 높으니 미래에 더 높은 고점을 찍을 가능성이 있으니까요.
이때 사용 연료량의 상한을 고정해 주면 비로소 현재 사용 연료량이 낮으면 반드시 좋다고 말할 수 있게 되고, DP로 풀 수 있는 문제로 바뀌는 것입니다.

dnjsgudtjr11   1년 전

감사합니다! 어제 혼자 계속 고민했었는데 덕분에 왜 틀렸는지 이해했습니다

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