3621 족보

구현문제

d = 2,3,4일때 부모의 수(a[i])를 변수로 두고 식을 세워보면

(a[i] - d + d - 2) / (d - 1) = (a[i] - 2) / (d - 1)이 나온다.

a[i]>d일 때 더해주면 끝

<코드>

#include <stdio.h>
 
int n, d, a[100001], t, ans;
 
int main() {
    scanf("%d%d", &n, &d);
    for (int i = 0; i < n; i++) {
        scanf("%d", &t);
        a[t]++;
    }
    for (int i = 0; i <= n; i++) if (a[i] > d) 
        ans += (a[i] - 2) / (d - 1);
    printf("%d", ans);
    return 0;
}