[백준 1231] 주식왕 동호

문제

https://www.acmicpc.net/problem/1231

 

알고리즘

knapsack

 

풀이

$D$일동안 갯수제한없는 knapsack을 하는 문제입니다.

 

그리디한 DP임을 눈치채야 풀 수 있습니다. A일에 사서 B일에 파는 것은 A+1일에 해당 주식을 팔지 말지 결정하고 팔았다면 무조건 재매수를 하는 것을 B일까지 반복하는 것과 동일합니다. 만일 10 15 20에 해당하는 주식이 있다면 10에 주식을 사서 3일째 되는 날 20에 팔아 10의 이득을 챙기는 것과 2일째에 15에 팔고 다시 15에 사서 20에 파는 것은 동일합니다.

즉 갯수제한이 없는 knapsack을 D-1일 동안 하는 것과 동일한 문제로 바뀌게 됩니다. 

 

$cache[i]$=  현재 사용가능한 돈이 $i$원일때, 얻을 수 있는 최대이익

 

위와 같이 DP배열을 만들어 0으로 초기화 한다면 현재 보고 있는 주식을 사는 것이 이득이라고 판단(어제보다 더 비쌈)되면 바로바로 주식을 팔아 이익을 실현하여 풀 수 있습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int C, D, M;
int stock[55][15];
int cache[500005];
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> C >> D >> M;
    rep(i, C) rep(j, D) {
        cin >> stock[i][j];
    }
    REP(j, D - 1) {
        memset(cache, 0, sizeof(cache));

        rep(i, C) {
            for (int k = stock[i][j - 1]; k <= M; ++k) {
                cache[k] = max(cache[k], cache[k - stock[i][j - 1]] + stock[i][j] - stock[i][j - 1]);
            }
        }
        M += cache[M];
    }
    cout << M;
    return 0;
}