[BOJ 23831] 백준 23831번 - 나 퇴사임?
1. 문제
$23831$. 나 퇴사임? (SASA Programming Contest 2021 Open Contest F번)
2. 풀이
- 정독실과 소학습실의 합이 $B$회 이상이다.
- 요양은 $A$회 이하이다.
- 휴게실은 이틀 연속으로 불가능하다.
이 세 가지 조건을 토대로 매 날마다 정독실&소학습실, 요양, 휴게실 세 가지 중 한 가지를 선택하며 만족도의 최댓값을 구하는 문제이므로 dp를 이용한다.
최대 $100$일이고 정독실&소학습실$(B)$, 요양$(A)$의 최댓값은 $100$이므로 $dp[101][101][101]$이라고 둘 수 있다. 휴게실은 횟수는 중요하지 않고 연속만 확인하면 되므로, 현재 휴게실을 사용했는지 안했는지를 표시하는 $0,1$로 충분하기 때문에 $dp[101][101][101][2]$로 완성할 수 있다. 이는 $101\times 101\times 101$ $\times 2\times (4byte)=8MB$이므로 무난한 메모리 양이다.
(휴게실 사용X -> $0$ / 휴게실 사용O -> $1$로 둔다.)
$1.$ dp[i][a][b][0] 구하기 (지금 휴게실 사용을 안 할 것이므로, $dp[i-1]$때 휴게실을 사용했든 안했든 상관이 없다.)
- $A = max(dp[i-1][a-1][b][0],$ $ dp[i-1][a-1][b][1]) + max(p[i], q[i])$ $\rightarrow$ 정독실&소학습실 사용
- $B = max(dp[i-1][a][b-1][0],$ $ dp[i-1][a][b-1][1]) + max(p[i], q[i])$ $\rightarrow$ 요양
- $dp[i][a][b][0] = max(A, B)$
$2.$ dp[i][a][b][1] 구하기 (지금 휴게실 사용을 할 것이므로, $dp[i-1]$때 휴게실을 사용하지 않았어야 한다.)
- $dp[i][a][b][1] = dp[i-1][a][b][0] + r[i] \rightarrow$ 휴게실 사용
정독실&소학습실 사용과 요양의 합이 $N$을 넘지 않으므로(휴게실 사용 횟수는 알 수 없음), $j$의 값을 $1\sim i$, $k$의 값을 $0\sim j$로 지정하고(코드 46~47줄),
dp[i][k][j-k][0 or 1]로 만든다. 이때, $k=0$ 이거나 $j-k=0$ 이면 $-1$을 할 수 없으므로 따로 예외처리를 한다.
$A$와 $B$의 제한을 dp 중간에 처리하기는 복잡해 보여서 그냥 제일 나중에 maximum 값을 갱신할 때 제한에 맞지 않는 값들을 skip하였다. 또한 불가능한 값들 처리는 초기값을 -INF로 두어서 아무리 더해도 $0$ 이상이 안되도록 하게 만드는 방식으로 처리하였다.
3. 채점 결과
4. 회고
타이핑 실수로 WA를 받았다.
댓글남기기