[BOJ 2516] 원숭이

문제

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

2516번: 원숭이

 

---

알고리즘

• 그리디
• 구성적

---

풀이

어려워 보이지만 잘 생각해보면 의외로 간단한 문제입니다.

먼저 모든 원숭이를 한 곳에 집어넣은 다음, 각 원숭이마다 같은 우리 안에 있으면서 앙숙관계인 원숭이가 2마리 이상이라면 그 원숭이를 다른 우리에 넣는 방식으로 풀어나가면 됩니다.

각 원숭이마다 앙숙관계인 원숭이가 최대 3마리이므로, 각 원숭이마다 최대 3번 이동시키면 답을 구할 수 있습니다.

 

---

전체 코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<int> g[100001], a, b;
    vector<bool> chk(N + 1);
    for (int i = 1; i <= N; ++i) {
        int M; cin >> M;
        for (int j = 0; j < M; ++j) {
            int n; cin >> n;
            g[i].push_back(n);
        }
    }

    bool flag = 1;
    while (flag) {
        flag = 0;
        for (int i = 1; i <= N; ++i) {
            int cnt = 0;
            for (auto &j : g[i])
                cnt += chk[i] == chk[j];
            if (cnt > 1) chk[i] = !chk[i], flag = 1;
        }
    }

    for (int i = 1; i <= N; ++i)
        chk[i] ? b.push_back(i) : a.push_back(i);

    if (!b.size()) b.push_back(a.back()), a.pop_back();

    cout << a.size() << ' ';
    for (auto &i : a) cout << i << ' ';
    cout << '\n';

    cout << b.size() << ' ';
    for (auto &i : b) cout << i << ' ';
    cout << '\n';

    return 0;
}

 

사실 증명하기 어려워 치트키(PBA)를 썼습니다.