boj 28325 호숫가의 개미굴

https://www.acmicpc.net/problem/28325

 

1 ~ N번 방은 서로 원형으로 연결되어 있으며, 각 방에는 Ci개의 쪽방이 있을 수 있습니다.

통로로 직접 연결되어 있는 두 방에는 하나의 개미만 들어갈 수 있으며, 개미굴에 살고있는 개미의 최대 수를 구하는 문제입니다.

 

문제의 카테고리가 dp와 그리디가 있었지만 저는 그리디로 해결했습니다.

우선 쪽방이 있다면 무조건 들어가는 것이 이득입니다.

쪽방은 i번 방의 바로 아래에 있는 자식 노드기 때문에 쪽방의 갯수를 세어주도록 합니다.

 

그 다음은 쪽방이 없는 나머지 방을 세어줍니다.

나머지 방에는 연속된 방으로 세어주시고, (연속된 방의 갯수 (cnt) + 1) / 2으로 구할 수 있습니다.

 

그것들을 정답에 더해주시면 되는데 마지막으로 생각할게 개미굴은 원형으로 되어있기 때문에 1번과 N번 방이 서로 연결되어 있습니다.

순회를 1번 방부터 했기 때문에 만약 1번과 N번 방 둘다 쪽방이 없다면 연속된 방의 갯수들을 합쳐줘야 합니다. (cnt + tmp)

그걸 위해서 처음에 1번 방부터 isFirst 변수를 추가하여 처음 연속된 빈방의 갯수를 tmp에 저장해두었습니다.

 

 

#include <iostream>
#define MAX 250001
using namespace std;
typedef long long ll;
 
ll list[MAX];
bool flag;
int N;
 
void func() {
    if (!flag) {
        cout << (N >> 1) << '\n';
        return;
    }
 
    ll ret = 0;
    ll cnt = 0;
    ll tmp = 0;
    bool isFirst = true;
    for (int i = 0; i < N; i++) {        
        if (!list[i]) cnt++;
        else {
            if (isFirst) tmp = cnt;
            ret += list[i];
            isFirst = false;
            ret += ((cnt + 1LL) >> 1);
            cnt = 0;
        }
    }
 
    if (!list[0] && !list[N - 1]) {
        ret -= ((tmp + 1LL) >> 1);
        ret += ((tmp + cnt + 1LL) >> 1);
    }
    else ret += ((cnt + 1LL) >> 1);
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
        flag |= list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}