[백준] 15486 - 퇴사2

삼성 기출문제 퇴사랑 같은 문제지만, 범위가 넓어서 DP로 푸는게 맞음

그냥 퇴사문제는 범위가 좁아서 DFS로도 풀 수 있지만 이 문제는 범위가 1500000이나 되기 때문에 DFS로는 절대 풀 수 없다

DP를 처음 공부하고 퇴사, 퇴사2를 풀면서 마스터했다

1. 일을 하고 다음 날 돈을 받는 걸로 생각한다

    ex. 3일 일하고 4일째 돈을 받는다. 따라서 N일까지 일을 한다고 가정할 때, N+1일날 돈을 받는다.

2. 오늘 부터 일을 할 때, map[i].day 이후, 즉 i + map[i].day 가 >N + 1일때는 일을 할 수 없으므로 continue;

3. i+map[i].day 되는 날 최대 값을 dp에 저장하고, 갱신하며 N + 1일까지 일을 한다.

#include <iostream>
#define MX_SIZE 1500002
#define MAX(X, Y) (X) > (Y) ? (X) : (Y)
using namespace std;
 
struct MAP {
    int day, pay;
}map[MX_SIZE];
 
long long dp[MX_SIZE];
int N, dab;
 
int main(void)
{
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> map[i].day >> map[i].pay;
 
    for (int i = 1; i <= N + 1; i++)
    {
        dab = MAX(dab, dp[i]);
        if (i + map[i].day > N + 1) continue;
        dp[i + map[i].day] = MAX(dab + map[i].pay, dp[i + map[i].day]);
    }
    cout << dab << endl;
    return 0;
}