[BOJ 24887] 백준 24887번 - 최대한의 휴식

		2022 숭고한 연합 알고리즘 콘테스트 Open Contest 풀이
A		[BOJ 24883] 자동완성
B		[BOJ 24884] 장작 넣기
C		[BOJ 24885] 주식
D		[BOJ 24886] SKH 문자열
E		[BOJ 24887] 최대한의 휴식
F		[BOJ 24888] 노트 조각
I		[BOJ 24891] 단어 마방진

1. 문제

$24887$. 최대한의 휴식 (2022 숭고한 연합 알고리즘 콘테스트 E번)

백준 24887번 - 최대한의 휴식 (https://www.acmicpc.net/problem/24887)

2. 풀이

연속해서 쉴 수 있는 기간의 최솟값의 최댓값, 즉 정답이 되는 값(이를 $x$로 간주한다)을 기준으로 이분탐색을 진행한다.

$N$일 모두 출근해도 할당량을 채울 수 없는 경우와 하루만에 할당량을 채울 수 있는 경우를 예외로 제외하면, $x$의 범위는 $0\leq x\leq N-2$이다.

여기서, 내 코드에서는 이후 계산의 편의성을 위해 $x$에 $1$을 더한 값을 $x$로 간주했다. 따라서 코드상으로 $x$의 범위는 $1\leq x\leq N-1$이다. 아래 계산도 전부 코드 기준으로 설명한다.

$left=1, right=N-1$로 이분탐색을 진행한다. 정해진 $mid$ 값이 간격의 최솟값이라는 조건에 따라서, 채울 수 있는 최대 할당량을 구하고

• 최대 할당량 $>= M$ $\,\rightarrow \, left=mid+1$
• 최대 할당량 $< M$ $\,\rightarrow \, right=mid-1$

으로 범위를 좁혀나가며 정답을 찾는다.

---

이제 간격의 최솟값이 정해졌을 때, 채울 수 있는 최대 할당량을 구하는 방법을 고안한다.

$dp[i] =$ 간격의 최솟값이 $mid$일 때, $\, i$일까지 얻을 수 있는 최대 할당량

이라고 간주했을 때, dp의 값은 다음과 같이 계산된다.

$dp[i] = max(dp[i-1],\, dp[i-mid]+W[i])$

• $dp[i-1] \rightarrow$ 당일에 일을 하지 않는 경우, 지금까지의 최댓값을 이어받음
• $dp[i-mid]+W[i] \rightarrow$ 당일에 일을 하는 경우, $mid$일 전까지의 최댓값을 이어받음

아래에 예시 하나를 정리해놓았다.

$N=11,\, M=20$
$1\,\,5\,\,2\,\,8\,\,4\,\,7\,\,2\,\,9\,\,8\,\,2\,\,8$
$mid=4$

i	1	2	3	4	5	6	7	8	9	10	11
W	1	5	2	8	4	7	2	9	8	2	8
dp	1	5	5	8	max(8,5)	max(8,12)	max(12,7)	max(12,17)	max(17,16)	max(17,14)	max(17,20)

3. 채점 결과

4. 회고

최대 할당량을 계산하는 방법이 dp임을 알기까지 꽤나 오래 걸렸다. 이런 상황에도 dp를 적용할 수 있다는 사실을 확실하게 알아놓아야겠다.

5. 코드