14501 퇴사

BOJ ::14501 퇴사

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

다이나믹프로그래밍 문제이다.

t+t[j]-1<= i 라는 조건을 통해 j번째 날부터 t[j]번째 시간을 더했을 때 일을 할 수있는 경우에 대해서

d[i]를 최대 비용으로 갱신 시킬 수 있도록 하였다.

#include <stdio.h>
using namespace std;
 
int n;
int t[16];
int p[16];
int d[16];
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &t[i], &p[i]);
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (j + t[j] - 1 <= i) {
                if (d[i] < d[j-1] + p[j]) {
                    d[i] = d[j-1] + p[j];
                }
            }
        }
    }
    printf("%d\n",d[n]);
 
}