BOJ 17521 - Byte Coin

링크: https://www.acmicpc.net/problem/17521

문제

보자마자 주식 문제가 생각났다.

주식 문제들은 최대 이익을 내기 위해서 그리디하게 행동하면 된다. 값쌀 때 사서 값비쌀 때 팔면 된다.

이 문제에서는 늘어난 코인만큼 다시 투자를 할 수 있으니, 상승 곡선이면 무조건 사는것이 이득이다. (늘어난 코인을 배로 불릴 수 있으니)

코드

직관적으로 풀었지만 내심 불안했다.

그래서 dp로도 풀어보았다. 물론, 같은 결과가 나왔고 정답이다.

점화식은 dp[k] := k일까지 벌 수 있는 최대 코인이다.

\(i < j\) 인 \(i\)일째에 가진 돈으로 전부 매수하고, \(j\)일에 모두 매도한다면 (두 날짜 사이의 변폭) * (i일에 살 수 있었던 코인의 수)만큼 벌 수 있을것이다.