ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 31413 |
문제명 | 입대 |
레벨 | 골드 3 |
분류 |
DP |
시간복잡도 | O(n^2) |
인풋사이즈 | n<=1000 |
사용한 언어 | Python 3.11 |
제출기록 | 31120KB / 316ms |
최고기록 | 316ms |
해결날짜 | 2024/02/23 |
출처 |
"""Solution code for "BOJ 31413. 입대".
- Problem link: https://www.acmicpc.net/problem/31413
- Solution link: http://www.teferi.net/ps/problems/boj/31413
Tags: [dp]
"""
def main():
N, M = [int(x) for x in input().split()]
s = [int(x) for x in input().split()]
A, D = [int(x) for x in input().split()]
v = 0
dp_cur = [v := v + s_i for s_i in reversed(s)][::-1]
if dp_cur[0] >= M:
print('0')
return
for j in range(1, N + 1):
dp_prev, dp_cur = dp_cur, [None] * N
dp_cur[N - 1] = max(s[N - 1], A)
for i in reversed(range(N - 1)):
if i + D < N:
dp_cur[i] = max(dp_cur[i + 1] + s[i], dp_prev[i + D] + A)
else:
dp_cur[i] = max(dp_cur[i + 1] + s[i], A)
if dp_cur[0] >= M:
print(j)
break
else:
print('-1')
if __name__ == '__main__':
main()