[백준] 23831번 : 나 퇴사임? (C++)

23831번 : 나 퇴사임?

---

문제)

SASA의 자습 시간에는 매일마다 정독실, 소학습실, 휴게실, 그리고 방에서 휴식을 취할 수 있는 요양 4가지 중 하나를 선택할 수 있다.

우석이는 자습 장소에 따라 얻을 수 있는 만족도가 있으며, 그 4가지 값은 매일 우석이의 기분에 따라 결정된다.

우석이는 자습을 총 N일 동안 해야 하며, 기숙사에는 다음과 같은 규칙이 있다.

• 요양 신청은 최대 A회 가능하다.
• 휴게실에서 이틀 연속으로 자습을 할 경우, 게임을 하는 것으로 판단되어 퇴사 처리된다.
• 정독실이나 소학습실에서 자습을 총 B회 미만으로 할 경우, 학습 의지 상실로 판단되어 퇴사 처리된다.

공부하기 싫은 우석이가 퇴사를 당하지 않고 기숙사의 규칙을 지키면서 N일 동안 얻을 수 있는 만족도의 합의 최댓값을 구해보자.

 

 

 

입력 :

첫째 줄에 자습일의 수 N이 주어진다.

둘째 줄에 가능한 요양 신청 횟수 A와 정독실과 소학습실에서 합쳐서 필수적으로 자습을 해야 하는 횟수 B가 주어진다.

셋째 줄부터 N 개의 줄의 i 번째 줄에는 4개의 정수 pi, qi, ri, si가 공백으로 구분되어 주어진다. 이 값은 i번째 자습일에 정독실, 소학습실, 휴게실 자습 및 요양을 할 때 얻는 만족도를 의미한다.

 

 

 

출력 :

기숙사의 규칙을 지키면서 N일 동안 얻을 수 있는 만족도의 합의 최댓값을 출력한다.

 

 

 

 

 

 

풀이)

 

// 23831. 나 퇴사임?
#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
int a, b;
vector<vector<int>> vec;
 
int dp[101][2][101][101];
 
// 이전에 휴게실을 사용하지 않았다면 prev = 0;
// 휴게실을 사용했다면 prev = 1
 
int recur(int cur, bool prev, int rest, int study)
{
    if (cur == n)
    {
        // 정독실이나 소학습실에서 자습을 b회 미만으로 한 경우 퇴사처리
        if (study < b) return -999999;
 
        return 0;
    }
 
    if (dp[cur][prev][rest][study] != -1) return dp[cur][prev][rest][study];
    
    int ret = -9999999;
 
    // 요양 신청을 한 경우
    if (rest < a) ret = max(ret, recur(cur + 1, false, rest + 1, study) + vec[cur][3]);
 
    // 이전에 휴게실을 사용하지 않았다면
    if (prev == false)
    {
        // 휴게실에서 자습을 할 수 있다.
        ret = max(ret, recur(cur + 1, true, rest, study) + vec[cur][2]);
    }
 
    // 정독실에서 자습을 한 경우
    ret = max(ret, recur(cur + 1, false, rest, study + 1) + vec[cur][0]);
 
    // 소학습실에서 자습을 한 경우
    ret = max(ret, recur(cur + 1, false, rest, study + 1) + vec[cur][1]);
 
    dp[cur][prev][rest][study] = ret;
 
    return ret;
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    cin >> a >> b;
    vec.resize(n, vector<int>(4));
    for (auto& ele : vec) for (int& e : ele) cin >> e;
 
    fill(&dp[0][0][0][0], &dp[100][1][100][101], -1);
 
    cout << recur(0, 0, 0, 0);
 
    return 0;
}
 

---

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

23831번: 나 퇴사임?