[백준] 31413 - 입대

[문제]

---

https://www.acmicpc.net/problem/31413

[풀이]

---

문제를 보고 2579의 계단 오르기가 떠올랐다.
헌혈을 할 때마다 D일을 쉰다면 최대 헌혈 횟수는 $\frac{N+D-1}{D}$ $(=ceil(N/D))$번이다.
0부터 최대 헌혈 횟수까지 전부 최대값을 구해주고 반복문을 돌면서 최소 헌혈 횟수를 구해줬다.

i일차와 헌혈한 횟수 j에 대해 가산점의 최대값은 dp[j][i]이다.
기본적으로 누적합을 적용하고, 헌혈했을 때를 따로 처리해준다.

코드를 보면 2중 반복문 안에 continue 부분 조건문은 이전 값이 0이라면 진행하지 않는 뜻이다.
이 부분이 없다면 계속 최대값으로 갱신되어 잘못된 계산을 할 수 있다.
예를 들어, 예제 1에서 2번 헌혈했을 때의 최대값과 3번 헌혈했을 때의 최대값이 같아지는 경우가 있다.

[코드]

---

import sys
r=sys.stdin.readline

N, M = map(int, r().split())
S = [0] + list(map(int, r().split()))
A, D = map(int, r().split())

upper = (N+D-1)//D # ceil(N/D)

dp = [[0 for _ in range(N+D)] for _ in range(upper+1)]
for i in range(1,N+1):
    for j in range(upper+1):
        if j != 0 and dp[j][i-1] == 0: continue
        dp[j][i] = max(dp[j][i], dp[j][i-1] + S[i])
        if j != upper:
            dp[j+1][i+D-1] = max(dp[j+1][i+D-1], dp[j][i-1] + A)

for i in range(upper+1):
    if max(dp[i]) >= M:
        print(i)
        break
else:
    print(-1)