[백준 20181] 꿈틀꿈틀 호석 애벌레 - 효율성 C++

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

다이나믹 프로그래밍, 투 포인터

코딩꿈나무 조정현 : 네이버 블로그

정현님의 추천문제를 풀어보았다!

---

1. 문제 해결 아이디어

 

[백준 1644] 소수의 연속합 C++

이때 풀었던 투 포인터 방법을 떠올려서 풀었다

 

기본동작 : st와 ed사이의 값의 합이 K(최소 만족도)보다 클 때까지 ed를 1씩 증가시킨다.

-> ed까지의 최대 에너지는 DP[ed] = max(DP[ed], DP[ed-1]) 코드를 통해서 항상 최댓값을 유지한다.

 

사이 합이 K이상인 경우 : st를 1씩 증가시킨다.

-> DP[ed] = max(DP[ed], DP[st-1] + temp_sum - K) 코드를 통해서

(st이전까지의 최댓값 + 새롭게 얻은 탈피 에너지)와 현재 최대 탈피 에너지를 비교한 후 최댓값으로 갱신한다.

 

st==ed인데 사이합이 K보다 큰 경우 : st와 ed를 1씩 증가시킨다.

---

2. 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int N, K;
long long feed[100001], DP[100001]; // dp[i] = i까지 먹이를 먹은경우 최대 축적 E
 
void input(){
    cin >> N >> K;
    for(int i = 1; i <= N; i++){
        cin >> feed[i];
    }
}
void solve(){
    int st = 1, ed = 1;
    long long temp_sum = feed[st];
    
    while(st <= N && ed <= N){
        // DP갱신
        DP[ed] = max(DP[ed], DP[ed-1]);
        
        // 누적 합이 최소 만족도 이상인 경우
        if(temp_sum >= K){
            DP[ed] = max(DP[ed], DP[st-1] + temp_sum - K);
            if(st < ed){
                temp_sum -= feed[st];
                st++;
            }
            else if(st == ed){
                st++;
                ed++;
                temp_sum = feed[ed];
            }
        }
        else{
            ed++;
            temp_sum += feed[ed];
        }
    }
    
    cout << DP[N];
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    input();
    solve();
    return 0;
}