조약돌 (JUNGOL 5122)

https://jungol.co.kr/problem/5122

---

아이디어

구간 [i,j]에서 인접한 두개씩 가져가는 행동만으로 가능한지 확인하는것은 O(N)의 시간이 걸립니다. dp[i]를 [1,i]의 조약돌을 모두 가져가기위한 행동의 최소 횟수라고 정의하면 [i+1,j]에서 두개씩 가져가는것으로 가능한 최소의 j에 대해 dp[j]=min(dp[j],dp[i]+1)을 수행해줄 수 있습니다. 이를 바탕으로 O(N) DP를 해주면 됩니다.

---

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll arr[2525]={0},dp[2525]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i;

    cin>>N;
    for (i=1;i<=N;i++) cin>>arr[i];

    for (i=1;i<=N;i++) dp[i]=1e18;
    for (i=1;i<=N;i++)
    {
        ll now=arr[i];
        for (ll j=i+1;j<=N;j++)
        {
            if (arr[j]<now) break;
            now=arr[j]-now;
            if (now==0)
            {
                dp[j]=min(dp[j],dp[i-1]+(j-i));
                break;
            }
        }
        dp[i]=min(dp[i],dp[i-1]+1);
    }

    cout<<dp[N];
}