23831 나 퇴사임? (백준, python3)

 

시간 제한	메모리 제한
1초	512MB

문제

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

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

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

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

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

입력

첫째 줄에 자습일의 수 N(1 ≤ N ≤ 100)이 주어진다.

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

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

출력

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

 

---

풀이

i번째 날까지의 상태를 이렇게 정리해 보자. 총 a회 요양을 신청했고 b회 정독실이나 소학습실에서 자습을 했다. 그리고 i번째 날 당일에 휴게실을 이용하는 경우와 이용하지 않는 경우가 있다.

 

i번째 날까지의 최대 만족도는 그 전날까지의 최대 만족도를 갖고 계산할 수 있다. i-1번째 날, 최대 만족도가 아닌 k가 i번째 날의 선택에 따라 최대 만족도를 구성할 수 있다고 가정해보자. 그렇다면 i번째 날의 어떤 만족도 x을 더하면 해를 얻을 수 있다. 그런데 i-1번째 날의 최대 만족도인 l에 x를 더하면 k + x < l + x 이므로 가정은 거짓이고, 모든 날에 대해 최대 만족도를 순차적으로 구하는 것으로 다음 날의 최대 만족도를 얻을 수 있다.

 

dp테이블을 이렇게 구성한다. dp[n][a][b][s] = n번째 날까지 a회 요양, b회 정독실 및 소학습실, s == 1인 경우 휴게실 자습.

 

정독실이나 소학습실이나 어디를 가도 b의 횟수에 포함되므로 둘 중 만족도가 큰 것만 따져보면 된다.

둘을 합쳐서 t라고 하겠다.

 

점화식을 다음과 같이 생각할 수 있다.

rest[i] = max(dp[i - 1][a - 1][b][0], dp[i - 1][a - 1][b][1]) + s[i]
study[i] = max(dp[i - 1][a][b - 1][0], dp[i - 1][a][b - 1][1]) + t[i]

dp[i][a][b][0] = max(rest, study)
dp[i][a][b][1] = dp[n - 1][a][b][0] + r[i]

 

탐색 방법은 순차적으로 하되 a + b는 i 이하여야만 하고, 휴게실을 이용하는 경우는 a + b가 i 미만인 경우만 확인한다.

 

 

정답 코드

import sys
input = sys.stdin.readline
def solution():
    N = int(input())
    A, B = map(int, input().split())
    sat = [tuple(map(int, input().split())) for _ in range(N)]
    sat.reverse()
    dp = [[[[0] * 2 for _ in range(101)] for _ in range(101)] for _ in range(101)]
    for n in range(1, N + 1):
        p, q, r, s = sat.pop()
        t = max(p, q)
        for b in range(n + 1):
            for a in range(n - b + 1):
                study, rest = 0, 0
                if a: rest = max(dp[n - 1][a - 1][b]) + s
                if b: study = max(dp[n - 1][a][b - 1]) + t
                dp[n][a][b][0] = max(study, rest)
                if a + b < n: dp[n][a][b][1] = dp[n - 1][a][b][0] + r
    high = 0
    for a in range(A + 1):
        for b in range(B, N + 1):
            high = max(high, max(dp[N][a][b]))
    print(high)
solution()