BOJ 15486) 퇴사 2

시간 제한 - 2s

메모리 제한 - 512MB

---

풀이

n일차와 n-1일차를 모두 비교해 n, n-1, n-2 .. 1일까지의 최대 값을 모두 비교하면서 그날 그날의 최대 값에 상담을 통해 n + t일의 최대 값을 누적해줌

배열로 전부 받고 탑다운으로 들어가도 되지만 메모리를 절약할 수 있다고 생각해서 배열 없이 입력 받으면서 동시에 처리해줌

입력

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

입력 값이 150만이라 입력 스트림을 튜닝안하면 바로 터짐

 

자료구조

n일 간의 최대 값을 담기 위한 int형 배열

 

로직

1. i째 날에 벌 수 있는 돈은 n일 전에 벌어놓은 돈 + n째 날에 상담을 했을 때 벌 수 있는 돈

2. i째 날에 벌 수 있는 최대의 돈은 1..i번째 날까지의 1. 중 최댓 값

3. 오늘까지의 최대 값 = 어제까지의 최대 값 vs n일 전의 최대 값 + n일부터 일했을 때 벌 수 있는 돈

---

 

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n, t, p;

	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;
	vector<int> dp(n + 2);	// n + 1일까지 벌 수 있는 금액의 누적합이 담김
	dp[0] = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> t >> p;
		dp[i] = max(dp[i], dp[i - 1]);	//	오늘까지의 최대 값
		if (i + t > n + 1) continue ;	//	종료일이 퇴사일 이후라면 PASS
		dp[i + t] = max(dp[i + t], dp[i] + p);	//	오늘 일을 했을 때 종료일까지의 최대 값 갱신
	}
	cout << max(dp[n + 1], dp[n]) << endl;	// 퇴사일까지의 최대 값
	return 0;
}

 

시간 복잡도

1부터 n + 1일까지 n일 동안 순회하므로 O(n)