https://www.acmicpc.net/problem/20925
문제요약
- 경험치를 최대로 만들면 됨
- 입장제한 경험치가 있고, 시간당 받는 경험치가 있고, 이동하는데 드는 시간이 있음
- 최대 1000분 동안
접근법
- 처음봤을때는 당황스러웠음
- [시간][던전] 에 있을 때 얻을 수 있는 최대 경험치를 기록하는 방식으로 해보았음
- 200 1000 200 시간 복잡도라 적절함
잘못 생각 했던 점
- 현재보다 더 많이 경험치를 주는 곳으로만 이동하면 된다고 생각했음
- 그런데 이동하는데 드는 시간이 있기때문에 a -> b를 가더라도, c를 거치고 갈때가 더 시간이 적게 드는 경우도 있음
- 그래서 저렇게 생각하면 안됨
newbieski