[백준 20181번] 파이썬 - 꿈틀꿈틀 호석 애벌 - 효율성

백준 20181 - 꿈틀꿈틀 호석 애벌레 - 효율성

시간 제한 1초, 메모리 제한 512MB

# 조건

• 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다.
• 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 수 있다.
• 또한 매초 1 만큼 오른쪽으로 무조건 진행한다.
• 호석 애벌레는 i 번째 먹이가 맛있을수록 높은 만족도를 얻는다.
• 호석 애벌레는 절제라는 것을 모르는 욕심쟁이기 때문에 한번 먹이를 먹기 시작하면 연속적으로 계속 먹어야 하며, 누적된 만족도가 최소 만족도 K 이상이 되거나 더 이상 먹을 먹이가 없을 때에 연속적으로 먹는 것을 멈춘다.
  • 만약 최소 만족도 이상이 되면 K 를 초과한 만족도만큼 탈피 에너지를 축적한다.
  • 직후에 호석 애벌레의 만족도는 다시 0 이 되고 먹이를 먹을 수 있게 된다.
• 나뭇가지를 전부 통과했을 때에 소화를 다 못 했을 경우에도 탈피 에너지는 최소 만족도를 넘기는 순간 이미 축적한 것으로 생각하자.

• 예를 들어 위와 같이 9개의 먹이가 존재하면, 호석 애벌레는 미래를 도모하여 1번 먹이를 과감하게 포기한다.
• 그리고 2번부터 먹기 시작해서 3번까지 먹으면 만족도가 9가 되어 3의 에너지를 축적하게 된다.
• 같은 이유로 4번 먹이도 포기하고 5번부터 먹으면 7번까지 연속으로 먹어서 15의 만족도를 얻는다.
  • 이를 통해 9의 탈피 에너지가 쌓인다.
• 8, 9번 먹이까지 먹게 되면 2의 탈피 에너지가 축적된다.
• 이렇게 얻은 총 14의 탈피 에너지가 위의 예제에서는 최대치이다.
• 매초마다 호석 애벌레는 오른쪽으로 이동하면서 먹이를 지나치거나 먹기 시작할 수 있다.
• 먹기 시작하면 만족도가 채워질때까지 먹게 될것이다.
• 어떤 먹이들을 대해 먹어야 축적된 탈피 에너지가 최대가 될 수 있을까?

입력

• 첫번째 줄에 먹이 개수 N, 최소 만족도 K 가 공백으로 주어진다.
• 두번째 줄에는 1 번부터 N 번 먹이의 만족도가 순서대로 주어진다.

출력

• 축적된 탈피 에너지의 최댓값을 구하라.
• 만약 탈피를 한 번도 할 수 없다면 0을 출력한다.

제한

• • 1 ≤ N ≤ 100,000, N 은 정수이다.
• 1 ≤ K ≤ 108, K 는 정수이다.
• 0 ≤ 각 먹이의 만족도 ≤ 108, 모든 만족도는 정수이다.

---

# 접근 방법

• 나뭇잎을 먹으며 현재 만족도를 투 포인터로 진행해주고, 최대 탈피 에너지를 저장하기 위하여 DP를 이용해주었다.
  • dp[i] : i번째까지의 최대 탈피 에너지
  • temp : 현재 만족도
• 투 포인터로 K이상이 될 때까지 right를 증가시키며 만족도를 더해준다.
  • while문을 right < N을 만족하는 동안 반복 시켜 준다.
  • 우선 temp += arr[right]를 통하여 현재 만족도를 증가 시켜준다.
  • 또한 right는 항상 최초의 방문을 보장하므로 (right는 +1씩 증가하므로) dp[right] = dp[right - 1]로 직전까지의 최댓값을 들고온다.
• temp가 K이상인 동안 while문을 내부에서 다시 돌려주며 아래와 같이 dp 값을 갱신해나간다.
  • dp[right] = max(dp[right], dp[left-1] + temp - K)
  • 현재 right의 값은 직전까지의 최댓값이 저장되어있으므로 이 값과
  • 현재 더해진 만족도가 시작하는 나뭇잎 인덱스 -1에 현재의 탈피 에너지를 더한 값 중 최댓값으로 저장해준다.
• 문제의 예를 살펴보자.
  1. 1 5 4 4 2 3 10 3 5 의 나뭇잎이 있고 left = 0, right = 0, temp = 0로 할당하고 while 문을 right <= N까지 시작한다.
  2. 처음은 1이므로 만족도는 1, k이상이 되기 위하여 right += 1을 해준다.
  3. 1 5 이므로 만족도는 6, 탈피 에너지는 0으로 dp[1] = 0가 된다.
  4. 이제 K 미만이 되어야 하므로 temp -= arr[left] = 5, left += 1이 되어 K보다 작아지게 되었으므로 다시 right += 1을 해준다. (left = 1, right = 2)
  5. 5와 4를 먹어 9의 만족도를 가지고 dp[2] = max(dp[2], dp[0] + 9 - K) = 3의 탈피에너지를 저장한다.
  6. 4번을 반복하며 left += 1을 해주고 left = 2, right = 2, temp = 4가 되므로 K이상을 먹기 위해 right += 1
     1. right + 1을 해준후 temp += arr[right]
     2. dp[right] = dp[right -1] 을 해주는 것이 중요!
     3. 현재까지의 dp = [0, 0, 3, 3, 0, 0, 0, 0, 0]
  7. dp[3]에는 직전까지의 최댓값인 3이 저장되어 있고 K = 4 + 4 = 8이 되므로 while문이 작동한다.
  8. dp[3] = max(dp[3], dp[left-1 = 1] + 8 - 6 = 2)가 되므로 그대로 3을 저장해준다.
• 이 문제에서는 같은 나뭇잎을 먹은 값 중 최댓값을 뽑아나가는 것이 핵심이라고 생각한다.
  • 이 로직을 위해서 먹지 않았을 때의 값 + 현재 충족하는 탈피 에너지를 구하는 것이 꽤나 까다로웠다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, K = map(int, input().split())  
arr = [0] + list(map(int, input().split()))  
dp = [0] * (N + 1)  

left, right, temp = 0, 1, 0  
while right <= N:  
    temp += arr[right]  
    dp[right] = dp[right-1]  
    while temp >= K:  
        dp[right] = max(dp[right], dp[left-1] + temp - K)  
        temp -= arr[left]  
        left += 1  
    right += 1  

print(dp[N])