BOJ 1231 - 주식왕 동호
개인적으로 생각하기 어려운 문제이다.
결론적으로 이 문제를 아이템의 개수 제한이 없는 Knapsack으로 치환이 가능하다.
어떠한 주식의 가격은 계속 연속적(?)임을 고려한다.
$1$일에 사서 $3$일에 파는 것을 $1 \to 3$ 으로 고려하지말고 $1 \to 2 \to 3$ 으로 고려해도 된다는 뜻이다.
이렇게 해석하면 각 일이 변할때마다 현재 가지고 있는 자본금 $M$을 바로 다음날과 현재 날과의 주식들의 가격 변동만을 이용해 얼만큼 불릴 수 있는지만 구하면 된다.
이를 $M'$ 라 하면 그 다음날에서 그 다다음날까지는 또 그 때의 주식 변화들로 $M'$ 를 자본금으로 하여 Knapsack을 하면 된다.
위에서 설명한 부분이 잘 이해가 안가기도 하는데, 주식이 하나만 있고 $1$일에 $100$ $2$일에 $50$ $3$일에 $200$ 인 주식이 있다고 하자.
$1 \to 2$ 일로 가는 DP에서는 $M$ 을 그대로 유지할 것이다. 왜냐면 가격이 더 떨이지기 때문이다.
$2 \to 3$일로 가는 DP에서는 $M$을 이용해 $50 \to 200$ 의 이득을 최대한 볼 것이다.
그런데 우린 $M$을 $1 \to 2$ 일에서 그대로 유지했으므로 사실 $1$일에 이 주식을 사서 $3$일에 파는 것과 동일하게 된다.
```c++
int dp[500001];
void solve() {
int C, D, M;
cin » C » D » M;
vvi W(C, vi(D));
fv2(W);
for (int d = 0; d < D - 1; d++) {
memset(dp, 0, sizeof dp);
for (int c = 0; c < C; c++)
for (int w = 0; w <= M; w++)
if (w - W[c][d] >= 0)maxa(dp[w], dp[w - W[c][d]] + W[c][d + 1] - W[c][d]);
M += dp[M];
}
cout « M;
}```
Comments