[백준] 5670 휴대폰 자판

어렵고 어렵고 어려운 트라이 문제다

트라이는 언제나 어렵다

트라이 그림을 그려보면 대충 문제 풀 수 있는 방법이 나온다

근데 처음에 짠 코드는 답도 잘나왔는데 계속 틀렸다. ㅎㅎ

단어를 다 입력 해주고 다시 하나하나 보며 

각 단어마다 몇번 눌러야 하는지 세주면 된다

세야하는 경우는

1) 루트일때

2) 길이 2개 이상일 때

3) 가는 도중에 끝나는 단어를 포함할 때 이다

트라이를 만들 때 NULL인 곳에 새롭게 동적할당 하면서 branch++ !

소스코드

#include <iostream>
using namespace std;
const int MAXN = 1e5 + 3;
char arr[MAXN][88];
bool ini;
int n,ans;
struct Trie {
    bool vaild;
    bool exist;
    int branch;
    Trie* node[26];
    Trie() :vaild(false), exist(false), branch(0) {
        for (int i = 0; i < 26; i++) node[i] = 0;
    }
    ~Trie() {
        for (int i = 0; i < 26; i++)
            if (node[i]) delete node[i];
    }
    void add(const char* s) {
        if (*s == 0) vaild = true; 
        else {
            int pos = *s - 'a';
            if (node[pos] == NULL) {
                branch++; node[pos] = new Trie();
            }
            exist = true;
            node[pos]->add(s + 1);
        }
    }
    void check(const char*s) {
        if (*s == 0) return;
        if (ini) {
            ans++; ini = false;
        }
        else {
            if (branch >= 2) ans++;
            else if (vaild) ans++;
        }
        int pos = *s - 'a';
        node[pos]->check(s + 1);
    }
};
int main() {
    while (scanf(" %d", &n) != -1) {
        Trie* root = new Trie();
        for (int i = 0; i < n; i++) {
            scanf(" %s", &arr[i]);
            root->add(arr[i]);
        }
        int total = 0;
        for (int i = 0; i < n; i++) {
            ini = true;
            ans = 0;
            root->check(arr[i]);
            total += ans;
        }
        printf("%.2lf\n", (double)total / n);
        delete root;
    }
}