20925. 메이플스토리

어떻게 문제 제목이..

20925번: 메이플스토리

---

딱 봐도 DP 문제이다. DP 식만 잘 정의하면 된다.

 

사냥터의 번호를 $i$, 현재 시간을 $j$라 할 때, 다음 두 가지의 식을 생각해볼 수 있다.

1. $dp[i][j]$: 지금부터 얻을 수 있는 경험치의 최댓값
2. $dp[i][j]$: 현재까지 얻을 수 있었던 경험치의 최댓값

저장된 값이 미래의 값인지, 과거의 값인지가 다르다. 처음에는 1번 식으로 풀어보려 했으나, 사냥터에 입장할 수 있는 최소 경험치라는 조건 때문에 1번 식을 사용할 수 없다. 미래의 값으로 과거의 조건을 유추해낼 수 없기 때문이다. 따라서 2번 식을 사용해야 한다.

 

사냥터 $i$에 있을 때 할 수 있는 행동은 두 가지이다.

1. $i$번 사냥터에서 1분간 사냥한다.
2. 사냥하지 않고 다른 사냥터 $k$로 이동한다. 단, $dp[i][j] \ge c[k]$여야 한다.

임의의 시간 $j$에 대해 1번 값을 계산하고, 시간 $j$와 사냥터 $i$에 대해 2번 값을 계산하면 된다. 이러면 $O(N^{2}T)$ 시간에 풀 수 있다.

---

역시 나는 DP를 못한다;;