Problem Solving/BOJ
20925. 메이플스토리
해스끼
2023. 3. 25. 15:18
어떻게 문제 제목이..
20925번: 메이플스토리
첫째 줄 사냥터 수 $N$ ($1 \le N \le 200$)과 방학 기간을 분 단위로 나타낸 $T$ ($1 \le T \le 1\,000$)가 주어진다. 다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마
www.acmicpc.net
딱 봐도 DP 문제이다. DP 식만 잘 정의하면 된다.
사냥터의 번호를 $i$, 현재 시간을 $j$라 할 때, 다음 두 가지의 식을 생각해볼 수 있다.
- $dp[i][j]$: 지금부터 얻을 수 있는 경험치의 최댓값
- $dp[i][j]$: 현재까지 얻을 수 있었던 경험치의 최댓값
저장된 값이 미래의 값인지, 과거의 값인지가 다르다. 처음에는 1번 식으로 풀어보려 했으나, 사냥터에 입장할 수 있는 최소 경험치라는 조건 때문에 1번 식을 사용할 수 없다. 미래의 값으로 과거의 조건을 유추해낼 수 없기 때문이다. 따라서 2번 식을 사용해야 한다.
사냥터 $i$에 있을 때 할 수 있는 행동은 두 가지이다.
- $i$번 사냥터에서 1분간 사냥한다.
- 사냥하지 않고 다른 사냥터 $k$로 이동한다. 단, $dp[i][j] \ge c[k]$여야 한다.
임의의 시간 $j$에 대해 1번 값을 계산하고, 시간 $j$와 사냥터 $i$에 대해 2번 값을 계산하면 된다. 이러면 $O(N^{2}T)$ 시간에 풀 수 있다.
역시 나는 DP를 못한다;;