백준15486 - 퇴사2

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

알고리즘 종류 : 동적계획법

솔 ? : 보고함

접근 방법: 뒤에서부터 해당 날짜의 최대 수익을 DP에 저장하며 첫날의 최대수익을 출력한다

1. 상담 날짜가 지나면 이전 날 최대수익을 가져옴
2. [X날에 상담을 했을때 수익]+[X상담에 드는 날만큼 빠진 수익]과 X날 전날까지의 수익을 비교해 더 큰놈을 DP 넣는다.

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

using namespace std;

int T[1500010];
int    P[1500010];
int DP[1500010];

int main(void) {
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d %d", T+i, P+i);
    }
    for (int i = N; i >= 1; i--) {
        //max(DP[i+1], P[i]+DP[i+T[i]]);
        if (i + T[i] > N + 1) {
            DP[i] = DP[i - 1];
        }
        else {
            DP[i] = max(DP[i + 1], P[i] + DP[i + T[i]]);
        }
    }

    printf("%d", DP[1]);

    return 0;
}

후기 : 난 멍청이다 난 멍청이다 난 멍청이다

잘설명된 링크 : [SWEA] 4881_배열 최소 합 (백트랙킹 이용)