[백준/BOJ] 27915 금광 C++ 풀이

[문제 링크]
https://www.acmicpc.net/problem/27915

[설명]

하나의 방은 한 기업만이 채굴할 수 있다. 이때, 어떤 두 방 x, y를 같은 기업이 채굴한다면, 이 두 방 사이의 거리는 홀수여야 한다. 예를 들어, x의 레벨 1, y의 레벨이 3이라면 거리는 짝수가 되므로 이는 조건을 만족하지 못한다. 따라서 x, y는 각각 홀수, 짝수 레벨 혹은 짝수, 홀수 레벨이어야만 한다. 또한, 한 기업이 3개 이상의 방을 관리하는 것은 불가능하다는 것을 알 수 있다.

이를 고려하여, 트리의 홀수 레벨 방과 짝수 레벨 방으로 나누어서 생각해보자. 각 기업들은 최대 두 개의 방을 짝수 레벨에서 하나, 홀수 레벨에서 하나 고를 수 있다. 그렇다면 홀수 레벨 방이 odd개, 짝수 레벨 방이 even개라고 한다면 최소 기업수는 max(odd, even)임을 알 수 있다.

[코드]

#include <iostream>
using namespace std;

int stage[100001];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, i, temp, odd = 1, even = 0;
    cin >> n;
    stage[1] = 1;
    for (i = 2; i <= n; i++) {
        cin >> temp;
        stage[i] = stage[temp] + 1;
        if (stage[i] % 2 == 0) even++;
        else odd++;
    }
    cout << max(odd, even);
}