BOJ 27524 : 점수 내기

• 문제 링크 : boj.kr/27524
• 난이도 : P3
• 태그 : 트라이

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

class Trie {
public:
    unordered_map<int, Trie*> children;
    ll end;
    ll M;

    Trie() {
        end = 0; 
        M = 0;
    }

    void insert(vector<int>& key, ll score) {
        this->_insert(key, 0, score);
    };
    bool find(vector<int>& key) {
        return this->_find(key, 0);
    };

private:
    void _insert(vector<int>& key, int index, ll score) {
        if(index == key.size()) {
            end = score;
        }
        else {
            int next = key[index];
            if(children.find(next) == children.end()) children[next] = new Trie;
            children[next]->_insert(key, index + 1, score);
        }

        ll temp = 0;
        for(auto u : children) {
            temp = max(temp, u.second->M);
        }
        M = temp + end;
    }
    bool _find(vector<int>& key, int depth) {
        if(depth == key.size()) return end;
        int next = key[depth];
        if(children.find(next) == children.end()) return false;
        return children[next]->_find(key, depth + 1);
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    Trie Mpre, mpre, Msuf, msuf;

    int q;
    cin >> q;
    while(q--) {
        string t;
        cin >> t;
        if(t[0] == '<') {
            string s;
            cin >> s;
            ll score;
            cin >> score;
            vector<int> temp(all(s));
            Mpre.insert(temp, score);
            mpre.insert(temp, -score);
        }
        if(t[0] == '>') {
            string s;
            cin >> s;
            ll score;
            cin >> score;
            vector<int> temp(all(s));
            reverse(all(temp));
            Msuf.insert(temp, score);
            msuf.insert(temp, -score);
        }
        if(t[0] == '+') {
            cout << Msuf.M + Mpre.M << "\n";
        }
        if(t[0] == '-') {
            cout << -msuf.M - mpre.M << "\n";
        }
    }

    return 0;
}

---

풀이

사용할 수 있는 문자에 입력으로 주어지지 않는 숫자가 있기 때문에 접두사와 접미사를 분리해서 생각해 볼 수 있다.

또한 최댓값을 구하는 쿼리를 작성하고, 이를 값을 반대로 적용하여 사용하면 최솟값을 구할 수 있다.

따라서 최댓값을 구하는 방법에 대해서만 생각하면 된다.

 

트라이를 구성하며, 트라이에 사용되는 end 값에 해당 문자열의 점수를 넣어준다.

각 노드의 mx값은 해당 노드를 거칠 때의 최댓값을 의미하는데, 이 mx값을 문자열이 입력될 때마다

(자식의 mx값들 중 최댓값) + end로 갱신한다.

 

이제 루트의 mx값을 이용하여 최댓값을 구할 수 있다.