퇴사_백준14501

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

14501번: 퇴사

DP문제인것 같기는 한데 뒤에 있는 값을 사용하여 구하는 것이 더 편한것 같아 뒤에서부터 앞으로 가는 다이나믹프로그래밍으로 풀었습니다.

경우의 수는 3가지 : 상담을 끝낼 수 없다, 상담을 끝낼 수 있지만 상담을 안한다, 상담을 한다

상담을 끝낼 수 없다 : 현재 위치의 오른쪽에 있는 DP의 값이 항상 최대치의 값이므로 오른쪽의 값 

상담을 한다 :상담이 끝난뒤에 얻을 수 있는 최대값과 오늘 상담으로 벌게될 돈의 합

상담을 하지 않는다 : 상담을 하지 않으므로 뒤에 벌게될 돈의 최대값과 동일

상담을 하는것과 안하는 것의 비교는 현재 DP위치 오른쪽이 지금까지구한 최대값 이므로 그 값과 오늘 상담을 하면 벌게 될 돈과 오늘 일을 하게 되면 끝나는 일 다음날부터 벌수 있는 돈의 최대값을 합한것과 비교하여 넣는다

그렇게 DP배열의 제일 앞에 제일 큰 수가 입력

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int arr[2][16];
int dp[16];
int n, k;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &arr[0][i], &arr[1][i]);
    }
    for (int i = n - 1; i >= 0; i--) {
        k = arr[0][i]; // 작업일수
        if (i + k <= n) { // 퇴사전에 일을 끝낼 수 있는지 체크
            dp[i] = max(dp[i+1], arr[1][i] + dp[i + k]); // 오늘 상담을 했을때와 하지 않았을 때를 비교하여 최대값
        }
        else {
            dp[i] = dp[i + 1]; // 일을 끝낼수 없다면 하지않았을 때의 값
        }
    }
    printf("%d", dp[0]);
    return 0;
}