꿈틀꿈틀 호석 애벌레 - 효율성

• 기본적으로는 간단한 DP이기는 하다.
• i번째 먹이를 먹기 시작했을때, i+x 번째 먹이까지 먹어야 최소 만족도 이상이 된다고 하자. 바꿔 적으면 sum(A[i…i+x])≥K 라면, dp[i+x] = max(dp[i+x], dp[i-1] + sum(A[i…i+x]) - K) 와 같은 식으로 dp를 업데이트 할수 있다.
• 여기에 추가해야 할것은, sum(A[i…i+x])≥K 인 x를 모든 i에 대해서 계산하는 것. 이것은 투 포인터 방법으로 O(n)에 구할수 있기는 하다.
• 그리고 신경써야 할것은, dp점화식 형태상, 현재 구하려는 dp값을 이전의 dp값들을 이용해서 계산하는 것이 아니라, 현재의 dp값을 이용해서 미래의 dp값을 갱신해야 하는 형태가 되어서 구현을 좀 신경써야 한다. 퇴사과 비슷한 유형.
• 그래서, 이 두가지를 조합해서 구현하려면 구현이 꽤 헷갈릴 요소들이 있다.. 투포인터를 쓸때도 내가 주로 쓰는 이터레이터 기반의 구현이 아닌, 인덱스 기반으로 짜야 했다. 그나마 처음에는 l,r 을 가지고 돌려서 코드가 좀 복잡했는데, 이것을 beg와 end를 갖고 돌리는 식으로 처리해서 많이 깔끔해졌다.
  • 변수명이 l,r이라는 것은 부분배열의 범위가 [l,r]이라는 것을, 변수명이 beg,end라는 것은 범위가 [beg,end) 라는 것을 함의한다..
  • 사실 구현하기 복잡할거 같으면 그냥 먼저 투포인터로 sum(A[i…i+x])≥K 인 x를 모든 i에 대해서 구해놓고, 그다음에 다시 루프 돌면서 dp값을 처리해주는 식으로 짜면 간명하긴 하다.
• 시간복잡도는 O(n)

"""Solution code for "BOJ 20181. 꿈틀꿈틀 호석 애벌레 - 효율성".

- Problem link: https://www.acmicpc.net/problem/20181
- Solution link: http://www.teferi.net/ps/problems/boj/20181

Tags: [DP]
"""


def main():
    N, K = [int(x) for x in input().split()]
    satis = [int(x) for x in input().split()]

    dp = [0] * (N + 1)
    beg, end = 0, 1
    satis_sum = satis[0]
    while beg < N:
        if satis_sum >= K or end == N:
            dp[end] = max(dp[end], dp[beg] + satis_sum - K)
            satis_sum -= satis[beg]
            beg += 1
        else:
            satis_sum += satis[end]
            end += 1
            dp[end] = dp[end - 1]

    print(dp[-1])


if __name__ == '__main__':
    main()