백준 15486 퇴사2 (C++)

15486번: 퇴사2

dp를 활용한 문제이다. 보통 기간이 주어진 문제의 경우 나는 뒤에서 부터 접근을 먼저 시작해본다. 역시 맞았었다. N-1부터 시작하여 반복문을 돌면서 dp에 해당 위치의 최고 금액을 저장해주었다. 간단하게 풀 수 있었던 문제였다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int, int> pii;

int N;
vector<pii> v;
int dp[1500001];

void solution() {
    for (int i = N - 1; i >= 0; i--) {
        int day = v[i].first;
        int price = v[i].second;

        if (i + day > N) {
            dp[i] = dp[i + 1];
        }
        else {
            dp[i] = max(dp[i + 1], dp[i + day] + price);
        }
    }

    cout << dp[0];
}

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

    cin >> N;

    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        v.push_back({ a,b });
    }

    solution();

    return 0;
}