[백준 28325번] 호숫가의 개미굴 (C++)

문제링크 : https://www.acmicpc.net/problem/28325

28325번: 호숫가의 개미굴

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll arr[250002];
ll result = 0;
ll cnt = 0;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N;
    cin >> N;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
        result += arr[i]; //쪽방 개미 수 더해주기
    }

    if(result == 0)
    {
        cout << N/2;
        return 0;
    }

    int front = -1, end = -1;
    for(int i=0; i<N; i++)
    {
        if(arr[i] && front==-1) front=i; //첫 굴 위치
        if(arr[i] && front!=-1) end=i; //마지막 굴 위치
    }

    for(int i=front; i<=end; i++) //첫 굴 ~ 마지막 굴 사이에 없는 굴 갯수 체크
    {
        if(!arr[i]) cnt++;
        else
        {
            result += (cnt+1)/2;
            cnt=0;
        }
    }

    int diff = front-1 + N-end; //마지막 굴 ~ 첫 굴 사이에 없는 굴 갯수 체크
    result +=(diff+1)/2;

    cout << result;
    return 0;
}

쪽방을 모두 활용하는 것이 최적해이므로 쪽방에 있는 개미들을 모두 더해주고 시작한다.

만약 쪽방이 하나도 없다면 N/2를 출력한다.

 

그리고 배열을 탐색하며 첫 굴의 위치와 마지막 굴의 위치를 저장한다.

첫 굴 ~ 마지막 굴을 탐색하며 사이에 굴이 없는 경우를 카운팅하고 이때 가능한 최대 갯수를 따로 더해준다.

 

이렇게 탐색을 하면 마지막 굴 ~ 첫 굴 사이도 따로 탐색을 해줘야 한다.

그렇기에 첫 굴 앞에 존재할 수 있는 없는 굴 갯수인 front-1에 마지막굴 뒤에 존재할 수 있는 N-end를 더해주고 최종 result를 출력한다.