[Algorithm]Baekjoon 14501번 : 퇴사

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

14501번: 퇴사

 
int n, a, b;
 
int days[17] = { 0 };
int moneys[17] = { 0 };
int dp[17] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> days[i] >> moneys[i];
    }
 
    int answer = 0;
 
    for (int i = 1; i <= n+1; ++i)
    {
        dp[i] = max(dp[i], answer);
 
        if (i + days[i] <= n+1)
        {
            dp[i + days[i]] = max(dp[i + days[i]], dp[i] + moneys[i]);
        }
        answer = max(answer, dp[i]);
    }
 
    cout << dp[n + 1];
}
 

 

해당 날짜에 일한거에 대한 보수는 소요일 이후에 받기 때문에, 소요일 이후의 dp값을 업데이트해준다는 느낌이다.

최대값은 계속 들고있으면서, dp[i]에도 계속 업데이트 해줘야한다. dp[i]는 해당날짜까지의 최대보수이기 때문이다.

 

주의해야할 점은, 최종출력에 dp[n]이 아니라 dp[n+1]을 해주는것이다. 왜냐하면 마지막 날짜에 소요 하루짜리 일을 하면 그것에 대한 반영은 n+1에 업데이트 되기 때문이다.