[백준 20181] 꿈틀꿈틀 호석 애벌레 - 효율성 (Python)

www.acmicpc.net/problem/20181

20181번: 꿈틀꿈틀 호석 애벌레 - 효율성

 

문제풀이

N, K, arr : 입력값

dp : i번째 까지의 최대 탈피 에너지 

lmax : 애벌레가 먹기 시작하는 구간에서 지금까지 얻었던 최대 탈피 에너지

tmp : 현재 만족도

left, right : 투 포인터

 

굉장히 까다로운 문제였다. 현재 만족도에 대해서 투포인터를 진행하면서 탈피에너지에 대한 정보도 저장해야 한다. 따라서 투포인터(Two-Pointer)와 DP(Dynamic Programming)을 모두 활용해야 한다. 

투포인터 활용 문제는 정답을 알면 쉬운데, 모르면 한도끝도 없이 어렵다 ㅠㅠ..

 

1. 투포인터를 이용해 만족도(tmp)가 K 이상이기 까지 arr[right]를 더하면서 right를 증가시킨다.

 

2. 현재 만족도가 K 이상일 경우, 탈피에너지를 갱신한다.

- 애벌레가 먹기 시작하는 구간에서 지금까지 얻었던 최대 탈피 에너지(lmax)와 현재 위치에서 얻은 탈피 에너지(tmp - K) 를 더한 값과, 현재 애벌레 위치에서의 탈피에너지(dp[right - 1] 중 큰 값으로 현재 위치의 탈피 에너지를 갱신한다.

- 현재 만족도 감소, left 증가

 

3. 현재 만족도가 K보다 작은데 애벌레가 배열의 끝까지 도달한 경우, 더이상 확인할 필요가 없으므로 종료한다.

 

코드

import sys

if __name__ == '__main__':
    N, K = map(int, sys.stdin.readline().split())
    arr = list(map(int, sys.stdin.readline().split()))

    dp = [0] * N # dp[i]: i번쨰 까지의 최대 탈피 에너지
    lmax, ans = 0, 0 # lmax : # 애벌레가 먹기 시작하는 구간에서 지금까지 얻었던 최대 탈피 에너지
    tmp = 0 # 현재 만족도
    left, right = 0, 0 # 투 포인터
    while True:
        if tmp >= K:
            lmax = 0 if left == 0 else max(lmax, dp[left - 1])
            dp[right - 1] = max(dp[right - 1], lmax + tmp - K)
            tmp -= arr[left]
            left += 1
        elif right == N: break
        else:
            tmp += arr[right]
            right += 1
    for i in range(N):
        ans = max(ans, dp[i])
    print(ans)

 

결과

 

위 풀이는 'giiro' 님의 C++ 풀이를 참고한 코드입니다.

giiro.tistory.com

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!