백준 28325

문제 

KOI 호숫가에 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 둥근 호수의 둘레를 따라 1부터 𝑁까지의 번호가 붙은 𝑁개의 방이 차례대로 원형으로 배치되어 있으며, 모든 𝑖 (1≤𝑖≤𝑁−1)에 대해 𝑖번째 방과 𝑖+1번째 방이, 그리고 𝑁번째 방과 1번째 방이 통로로 직접 연결되어 있는 형태였다.

하지만 여러 이유로 인해 각 방에서 몇 개의 쪽방이 갈라지기 시작해서, 현재는 모든 𝑖 (1≤𝑖≤𝑁)에 대해, 개미굴의 𝑖번째 방에 𝐶𝑖개의 쪽방이 통로로 직접 연결되어 있다. 𝑖번째 방과 연결된 쪽방은 𝑖번째 방 이외에 다른 방과 통로로 연결되어 있지 않다.

예를 들어 𝑁=7이고, 𝐶=[3,0,0,1,0,2,0]인 개미굴은 아래 그림과 같은 형태이다.

개미굴의 각 방과 쪽방에는 최대 한 마리의 개미가 살 수 있다. 만약 통로로 직접 연결되어 있는 두 곳(방 또는 쪽방) 모두에 개미가 살고 있다면, 두 개미는 서로 불편해한다. 이러한 불편함을 방지하기 위해, 현재 개미굴의 각 통로가 직접 연결하는 두 곳 중 최대 한 곳에만 개미가 살고 있다.

개미들은 똑똑하기 때문에, 이 조건을 만족하는 하에 최대한 많은 수의 개미들이 현재 개미굴에 살고 있다고 한다. 현재 개미굴의 구조가 주어질 때, 개미굴에 살고 있는 개미의 수를 구하는 프로그램을 작성하라.

풀이

조건부로 풀면 된다. 그리디 알고리즘에 가까운 것 같다. 

쪽방은 무조건 한개 이상이다. 그러므로 특정한 방에 쪽방이 있으면, 그 방에는 무조건 하나 이상의 개미가 들어가 살 수 있고, 그 옆방 두개에도 개미가 들어가서 살 수 있다.

그러므로 쪽방이 있다면 무조건적으로 체크해야하고, 쪽방과 쪽방 사이의 방의 개수를 계산하여 개미가 얼마나 들어와서 살 수 있는지 생각하면 된다.

원형인 점만 주의해서 문제를 해결하면 된다.

쪽방에 들어가는게 무조건 좋은거같긴한데, 증명을 못하겠다. 귀류법으로 하면 되나?

코드

#include <iostream>
#include <vector>
#define ll long long
using namespace std;
ll N, arr[250001], ans;
vector<int>v, dist;
int main() {
    cin>>N;
    for(int i=0; i<N; i++) {
        cin>>arr[i];
        if(arr[i]) {
            ans += arr[i];
            v.push_back(i);
        }
    }
    if(v.empty()) {
        cout<<N/2;
        return 0;
    }
    else if(v.size() == 1) {
        dist.push_back(N - v.size());
    }else{
        for(int i=0; i<v.size(); i++) {
            if(i == v.size()-1)
                dist.push_back(v[0] + N-1-v[i]);
            else 
                dist.push_back(v[i+1]-v[i]-1);
        }
    }
    for(auto e : dist){
        ans += e/2 + e%2;
    }
    cout<<ans;


}