어떤 사람이 아이디어를 받아들이기 위해서는 그 사람의 모든 친구들이 이미 아이디어를 받아들인 상태여야 한다.

이 문제는 최대독립집합(maximum independent set)을 구하는 문제와 동치이다. 이 문제에서 주어진 친구 관계도가 트리 형태인데, 이 트리로부터 어떤 노드를 루트로 하는 rooted 트리로 만들고 다음과 같이 부분문제 D를 정의한다.

(x=0이면 i를 얼리 아답터로 두지 않음, x=1이면 i를 얼리 아답터로 둠)

D[i][0]: i의 모든 child c에 대한 D[c][1]들의 합
D[i][1]: 1 + (i의 모든 child c에 대한 min(D[c][0], D[c][1])들의 합)

마지막에 min(D[root][0], D[root][1])을 구하면 이 값이 답이 된다. 이 방법의 시간복잡도는 O(N)으로 rooted 트리를 구성할 때 재귀함수를 사용할 경우 스택 overflow가 날 수 있으므로 주의해야 한다.

O(N³)의 알고리즘으로 이분매칭을 하여 해결하면 40% 정도, O(N²)의 알고리즘을 사용하여 문제를 풀면 60% 정도의 점수를 받는다.