BOJ #5670 - 휴대폰 자판

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <string.h>
#include <utility>
#include <vector>

#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define fup(i, a, b, c) for (int(i) = (a); (i) <= (b); (i) += (c))
#define fdn(i, a, b, c) for (int(i) = (a); (i) >= (b); (i) -= (c))
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int T, N;
string s;

const int GO_MAX = 26;

struct Trie {
    Trie *go[GO_MAX]; // 다음 노드를 가리키는 포인터 배열
    bool end;
    int child;
    int words;

    // 생성자
    Trie() : end(false), child(0), words(0) {
        fill(go, go + GO_MAX, nullptr);
    }
    // 소멸자
    ~Trie() {
        for (int i = 0; i < GO_MAX; i++)
            if (go[i])
                delete go[i];
    }
    // 문자열 key를 현재 노드부터 삽입
    void insert(const char *key) {
        if (*key == '\0') {
            child++;
            end = true;
        } else {
            int next = *key - 'a';
            if (!go[next]) {
                child++;
                go[next] = new Trie;
            }
            words++;
            go[next]->insert(key + 1);
        }
    }

    ll autoComplete(bool isRoot = false) {
        ll res = 0;
        if (isRoot || child > 1)
            res = words;

        fup(i, 0, GO_MAX - 1, 1) {
            if (go[i])
                res += go[i]->autoComplete();
        }

        return res;
    }
};

int main() {
    while (scanf("%d", &N) > 0) {
        Trie root;

        fup(i, 1, N, 1) {
            char tmp[81];
            scanf("%s", tmp);
            root.insert(tmp);
        }

        printf("%.2lf\n", root.autoComplete(true) / (double)N);
    }
}