백준 15486번 - C++

#include <bits/stdc++.h>
using namespace std;


// 1. 테이블 정의하기 : D[i]= ix2에서 타일을 붙이는 경우의 수
// 2. 점화식 정의하기 : D[k]=D[k-1]+D[k-2]+D[k-2] // D[k-2]에서 =를 추가하는 방법과 ㅁ을 추가하는 방법
// 3. 초기값 정의하기 : D[1]=1 , D[2]=3


int D[1500010];
int S[1500010][2];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;

	
	for (int i = 1; i <= n; i++) {
		cin >> S[i][0] >> S[i][1];
	}
	if (n == 1) { if (S[1][0] == 1)cout << S[1][1]; else cout << 0; return 0; }
	for (int i = 1; i <= n; i++) {
		D[i] = max(D[i], D[i - 1]);
		if (i + S[i][0] - 1 > n) continue;
		D[i + S[i][0]] = max(D[i + S[i][0]], D[i] + S[i][1]);
	}
	cout << *max_element(D + 1, D + n + 2);
}