코드 복사/붙여넣기 하는 당신이 아름답습니다.

15267 : Justified Jungle

풀이

트리를 일단 나눴다면, 나눠진 후의 모든 컴포넌트에 속한 노드 수는 같아야 한다.

즉, 노드는 n의 약수로만 나눠질 수 있다.

100만 이하 자연수의 약수 개수가 최대 240개니까

O(240*n) 잘 커팅하면 6초 안에 될 거 같은데 안 됨 흠…

아무튼 나이브하게는 안 돌아가므로 조금 더 생각을 해야한다.

트리를 돌며 gcd(서브트리의 노드 개수, n)의 개수를 세어주자.

음… 그냥 코드를 보는 게 더 빠르겠다.

코드

#include <cstdio>
#include <vector>
using namespace std;

int n, cnt[1000001];
vector<int> d, res, gph[1000001];

int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

int go(int now, int prv) {
    int ret = 1;
    for (int nxt : gph[now]) {
        if (nxt != prv) ret += go(nxt, now);
    }
    cnt[gcd(ret, n)]++;
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d %d", &u, &v);
        gph[u].emplace_back(v);
        gph[v].emplace_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!(n%i)) d.emplace_back(i);
    }

    go(1, 0);

    for (int i = 0; i < d.size(); i++) {
        for (int j = i + 1; j < d.size(); j++) {
            if (!(d[j]%d[i])) cnt[d[i]] += cnt[d[j]];
        }
    }

    for (int i = (int)d.size()-2; i >= 0; i--) {
        if (cnt[d[i]] == n/d[i]) printf("%d ", n/d[i]-1);
    }

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-14 18:05

Read more posts by this author