ABC344 F - Earn to Advance

Competitive Programming C++ AtCoder Algorithms

2024-03-09

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc344/tasks/abc344_f

원문 링크
https://atcoder.jp/contests/abc344/editorial/9473

\(1\)번째 선택지를 [소지금을 \(P_{i, j}\) 늘린다]가 아닌 [소지금을 지금까지 과금한 모든 칸에 대해 \(P_{i, j}\)의 \(\max\)만큼 늘린다]로 두고 풀어도 답은 같습니다.

따라서, 돈이 필요하게 되는 시점에서야 벌면 되며, 이를 이용해 이동경로를 고정했을 때 최적인 행동(중 하나)을 특정할 수 있습니다.

특히, 이동경로 중에서 필요한 정보는 [지금까지 통과한 칸 전체에 대해서 \(P_{i, j}\)의 \(\max\)]만큼 있으므로, \(dp[c][p]\)를 [칸 \(c\)에 있으면서, 지금까지 통과한 모든 칸에 대해서 \(P_{i, j}\)의 \(\max\)가 \(p\)일 떄의 (행동횟수, 소지금) 쌍의 최적치(행동횟수가 최소, 행동횟수가 같다면 소지금이 최대가 되는)]로 정하고 DP를 할 수 있습니다.

이 DP는 상태의 수가 \(O(N^4)\), 전이에(map 등을 이용해서) \(O(1)\)걸리는 것으로부터, 전체 \(O(N^4)\)의 시간에 계산할 수 있습니다.

상태 안 좋아서 한 주 쉬고난 뒤라 성적도 처참

지난주에 몸 상태가 별로라 한 주 쉬었더니 풀 수 있는데서 많이 버벅여서 아쉬웠다.
D번을 백트래킹으로 착각해서 상수커팅하다 1시간 날렸고, E번은 링크드 리스트를 잘못 구현해서 시간 내에 못풀었다.

D를 처음부터 DP써서 잘 풀고 E도 무난히 넘겼다면 F까지 볼 수 있었을텐데 하는 아쉬움이 남는다.