백준 퇴사 2(복습)

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

15486번: 퇴사 2

다시 풀엇는데 1일이나 걸렸고 

sum[i] = max(sum[i+1], lists[i].cost + sum[nextday]);

 sum[i+1] 누적값에 뒷부분과 현재에서 미래의 가져갈 누적값 합의 비교를 해야하는게 키포인트입니다. 

struct Data {
	int day;
	int cost;
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//퇴사
	//n+1
	//n일 최대한 많은 상담을 하려한다
	//ti pi 
	//n=7
	//비서에게 최대한 많은 상담을 잡으라고 부탁을 했거
	//비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아 놓앗다
	//각각의 상담은 상담을 완료하는데 걸리는 기간 ti pi이러진다
	//n=7
	long long n;
	cin >> n;
	vector<Data>lists;
	vector<int>sum(n+1,0);
	for (long long i = 0; i < n; i++) {
		int day,cost;
		cin >> day >> cost;
		Data d;
		d.day = day;
		d.cost = cost;
		
		lists.push_back(d);
	
	}
	int maxs = 0;
	for (int i = lists.size()-1; i >= 0; i--) {
		int nextday = lists[i].day + i;
		//cout << nextday << ",";
		
		if (nextday > n) {
			sum[i] = sum[i + 1];
			continue;
		}

		sum[i] = max(sum[i+1], lists[i].cost + sum[nextday]);
	}
	
	sort(sum.begin(), sum.end(), greater<>());
	cout << sum[0];
	
	return 0;
}