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

접근

• 20167-꿈틀꿈틀 호석 애벌레 - 기능성 문제의 상위 버전이다.
• N이 100,000까지 이므로, 완전탐색으로 접근은 불가능하고, 동적계획법을 생각해야했다.
• dp[i]를 i번째 먹이까지의 최대 누적 탈피에너지 값으로 정의했다.
• 포인터로 사용할 변수l과 r을 만족도의 함은 sum변수로 관리했다.
• 진행되는 과정은

1. r을 1증가 시킨다.

• 그에따라 r인덱스의 만족도를 sum에 더해준다.

2. 현재 만족도가 최소만족도 보다 큰경우

• 현재 만족도가 최소만족도보다 작아질 때까지l을 1씩 증가시키며 dp[r]값을 dp[r]과 dp[l]+sum-k 즉 l지점까지의 탈피에너지의 최대값+현재 l~r지점의 탈피에너지값 중 최대값을 저장시켜준다.
• l이 증가함에따라 sum에서 빼준다.

3. 최종적으로 dp[n]에 저장되어있는 값이 문제가 원하는 답이된다.

코드(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,k,sum,arr[100010],dp[100010];

int main(){
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>arr[i];
    for(int r=1,l=0;r<=n;r++){
        sum+=arr[r];
        dp[r]=dp[r-1];
        while(sum>=k){
            dp[r]=max(dp[r],dp[l]+sum-k);
            sum-=arr[++l];
        }
    }
    cout<<dp[n]<<"\n";
    
    return 0;
}

결과