백준 15468 C++

처음에는 날짜를 골라서 fill로 다 초기화할까 생각했는데 너무 비효율적인 것 같고

결국 이전값 중에서 최대값과 여기까지 쌓인값 + cost 뭐가 큰지 비교해야해서

그냥 이전값 중 최대값을 계속 갱신을 했다.

 

이전 값 중 최대값과 현재값을 비교해야하면 이전 값 중 최대값을 변수로 하나 지정해서

계속 최대값을 갱신하면 되겠다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;		//1<=n<=1500000
pair<int, int> p[1500010];		//걸리는 날짜, 받는 돈
int dp[1500010];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;

	int result = 0;
	int cur = 0;
	int day, cost;
	for (int i = 0; i < n; i++) {
		cin >> day >> cost;
		
		cur = max(cur, dp[i]);		//이전의 dp[i]의 값들과 현재 dp[i]의 값과 비교한다.

		if (i + day < n) {
			dp[i + day] = max(dp[i + day], cur + cost);			//이전에 언젠가 dp에 넣었던 값 vs 이전 dp들 중 최대값 + 받을 돈이냐
			result = max(result, dp[i + day]);
		}
	}
	cout << result;
}