[ boj : 1231 ] 주식왕 동호

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

1231번: 주식왕 동호

해설 : 하...졸립지만 이 문제만 해설하고 자겠습니다.

 

매우매우매우...어려웠던 문제였습니다. ㅠㅠㅠ

먼저 매일 주식을 팔지 안팔지 선택할 수 있습니다. 이 모든 경우의 수를 다해보기엔 많은 시간이 걸리게 되죠. 

그럼 이것을 어떻게 잘 최적화를 시켜야 되는데 한번 살펴봅시다.

 

먼저 오늘 주식이 내려갔는데 팔게된다면 그건 무조건 손해죠. 변동이 없다면? 파나 그냥 가지고 있으나 변화가 없습니다. 그럼 오를때 판다면? 무조건 이득이죠.

 

즉, 주식이 오른다면 무조건 그날에는 팔아버리는 것입니다. 다음날 살지 안살지는 지금 정하는 것이 아니라 다음날 정하는 것이죠.

 

오늘 소지금 M 으로 살수 있는 주식은 전부 사들이고 이때 M원일때 가질 수 있는 총 자본을 구해두는 것 입니다. 

어떻게???각 날마다 반복문을 통해서 매번 값을 갱신해 주면서요.

??어디서 많이 본 문제같지 않나요??

 

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

2294번: 동전 2

사실상 이 문제를 엄청나게 깊게 숨겨둔 문제입니다.(unbounded knapsack problem)

 

이 행동을 각 날마다 반복해서 해주면 됩니다.

다만 테이블 정의를 확실히 해줍시다.

 

dp[j] = 소지금 j원으로 가질 수 있는 최대 자본값어치

 

이때 '자본의 값어치'는 (내가 가지고 있는 소지금 + 주식의 가치) 가 됩니다. 그러므로 (오늘 주식의 가치 - 어제 주식의 가치)가 '오늘 발생한 소지금'이 되겠죠.

 

dp[j] = max(dp[j] , dp[j-arr[k][i]] + arr[k][i] + arr[k][i-1])

 

이렇게 점화식을 정의해 줄 수 있습니다.

 

근데 우리가 구하고자 하는 답은 결국 마지막날의 총자본의 가치이니, 매일마다 발생하는 '차액'을 초기자본에다가 계속 더해주면 바로 정답이 됩니다.

3중 for문을 돌려서 구해줄 수 있겠네요. 시간복잡도는 O(n*c*m) 이 되겠죠.

 

#include<bits/stdc++.h>

using namespace std;

int n, c, m;
int dp[500010];
int arr[55][15];

int main()
{
	cin >> n >> c >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < c; j++)
			cin >> arr[i][j];

	for (int j = 1; j <c; j++)
	{
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < n; i++) {
			for (int k = 1; k <= m; k++) {
				if (k - arr[i][j-1] < 0)continue;
				dp[k] = max(dp[k], dp[k - arr[i][j-1]] + (arr[i][j] - arr[i][j - 1]));
			}
		}
		m += dp[m];
	}
	cout << m;
	return 0;
}