호숫가의 개미굴 (JUNGOL 5754)

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

---

아이디어

쪽방이 있는 개미굴은 무조건 쪽방을 쓰는것이 이득입니다.

증명) 쪽방이 있는 i번째 방에 대해서 그 개미굴의 쪽방을 쓰지 않는 최적해가 존재한다고 가정해봅시다. 이 경우에 i번째 방을 쓰는지와 관계 없이 i번째 방을 사용하지 않고 그 쪽방을 사용하면 전체 사용하는 방의 개수가 감소하지 않게 됩니다. 그러므로 항상 쪽방을 사용하는것이 이득입니다.

 

그러면 쪽방이 있는 방은 사용할 수 없게 됩니다. 그러면 배열 상에서 쪽방이 없는 연속한 방의 개수가 k개이면 (k+1)/2의 버림값이 사용할 수 있는 방의 개수가 됩니다. 이를 계산해주면 됩니다.

---

소스코드

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

ll arr[252525]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,res=0,Start=-1;

    cin>>N;
    for (i=0;i<N;i++)
    {
        cin>>arr[i];
        if (arr[i])
        {
            res+=arr[i];
            if (Start==-1) Start=i;
        }
    }

    if (Start==-1)
    {
        cout<<N/2;
        return 0;
    }

    ll cnt=0;
    for (i=Start;i<N;i++)
    {
        if (arr[i])
        {
            if (cnt<0) continue;
            res+=(cnt+1)/2;
            cnt=0;
        }
        else cnt++;
    }
    for (i=0;i<Start;i++)
    {
        cnt++;
    }
    res+=(cnt+1)/2;

    cout<<res;
}