사용자 도구

사이트 도구


ps:problems:boj:20181

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

ps
링크acmicpc.net/…
출처BOJ
문제 번호20181
문제명꿈틀꿈틀 호석 애벌레 - 효율성
레벨골드 2
분류

DP, 투포인터

시간복잡도O(n)
인풋사이즈n<=100,000
사용한 언어Python
제출기록41896KB / 160ms
최고기록188ms
해결날짜2022/02/27

풀이

  • 기본적으로는 간단한 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()

토론

댓글을 입력하세요:
C M I Q B
 
ps/problems/boj/20181.txt · 마지막으로 수정됨: 2022/02/28 13:35 저자 teferi