[백준] 22864번 : 피로도 (C++)

22864번 : 피로도

---

문제)

하루에 한 시간 단위로 일을 하거나 일을 쉬어도 된다. 하루에 한 시간 일하면 피로도는 A만큼 쌓이고 일은 B만큼 처리할 수 있다.

만약에 한 시간을 쉰다면 피로도는 C만큼 줄어든다. 단, 피로도가 음수로 내려가면 0으로 바뀐다. 당연히 일을 하지 않고 쉬었기 때문에 처리한 일은 없다.

피로도를 최대한 M을 넘지 않게 일을 하려고 한다. M을 넘기면 일하는데 번아웃이 와서 이미 했던 일들도 다 던져버리고 일을 그만두게 된다.

번아웃이 되지 않도록 일을 할때 하루에 최대 얼마나 일을 할 수 있는지 구해보자. 하루는 24시간이다.

 

 

 

입력 :

첫 번째 줄에 네 정수 A, B, C, M이 공백으로 구분되어 주어진다.

맨 처음 피로도는 0이다.

 

 

 

출력 :

하루에 번 아웃이 되지 않도록 일을 할 때 최대 얼마나 많은 일을 할 수 있는지 출력한다.

 

 

 

 

 

 

풀이)

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int a, b, c, m;
int dp[25][1000010];
 
// 메모이제이션을 이용한 풀이
int recur(int cur, int rate)
{
    // 최대값을 찾을 것이므로 ret = 0로 초기화한다.
    int ret = 0;
 
    // 이미 최대값을 구한 값이라면 바로 결과를 return해준다.
    if (dp[cur][rate] != -1)
    {
        return dp[cur][rate];
    }
 
    if (cur == 24) return 0;
 
    for (int i = 0; i < 2; i++)
    {
        
        if (i == 0 && rate + a <= m)
        {    // 최대 피로도를 넘지 않는다면 일을 한다.
            ret = max(ret, recur(cur + 1, rate + a) + b);
        }
        else
        {    // 휴식을 취한다 (단 음수로는 내려가지 않음)
            ret = max(ret, recur(cur + 1, max(0, rate - c)));
        }
    }
 
    // 위의 두가지 방법중 최대의 ret를 찾는다.
 
    // 해당 단계에 저장한다.
    dp[cur][rate] = ret;
 
    return dp[cur][rate];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> a >> b >> c >> m;
 
    fill(&dp[0][0], &dp[24][1000010], -1);
    cout << recur(0, 0);
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/22864 

22864번: 피로도