[삼성 기출 문제] 백준 14501 퇴사

문제 링크

클릭시 이동합니다.

어떻게 풀까?

현재가 X일이 지난 상태이고 일을 할 수 있는 상태라고 가정해봅시다!

그럼, X일 에서의 의뢰를 수행할 수 있겠죠! 이 일을 할 때 벌어들인 금액이 가장 최댓값이 되기 위해서는 어떻게 해야할까요?

답은 간단합니다! X일 전까지 일했던 금액이 가장 많게 하면 되죠!

현재가 X일이라고 했을 때, X-1+T[X]일의 금액 값과, X-1일까지 마친 금액 + P[X] 값 중 큰 값을 X-1 + T[X]일의 벌이로 기록하는 것입니다!

이렇게 하면, n일에 저장된 값을 바로 출력하면 되죠!

이를 위해, 간단한 DP점화식을 만들 수 있죠.

그리고, 인덱스 오류를 피하기 위해서 X +T[X]가 n을 넘어갈 때에는 무시하도록 합시다!

코드

#include<iostream>
#include<cstring>
#include<cstdio>
 
using namespace std;
typedef enum {Time = 0, Price = 1, size} type;
int info[2][16];
int retireMax[16];
 
inline int Retire_Max(int i1, int i2)
{
    return i1 > i2 ? i1 : i2;
}
 
int main()
{
    memset(retireMax, 0, sizeof(retireMax));
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d\n", &info[Time][i], &info[Price][i]);
        if(info[Time][i] + i - 1 <= n) retireMax[info[Time][i] + i - 1] = Retire_Max(retireMax[info[Time][i] + i - 1], retireMax[i-1] + info[Price][i]);
        retireMax[i] = Retire_Max(retireMax[i], retireMax[i-1]);
    }
 
    printf("%d\n", retireMax[n]);
 
    return 0;
}

시간 복잡도

 

반복문이 n까지 반복되기 때문에 시간복잡도는 O(N) 입니다.