[BOJ] 백준 17365. 별다줄 (Platinum III)

이번에도 UCPC 문제 포스팅이다.

트라이 구현코드를 바꾼 후, 처음으로 해결해본 응용 문제인데, 구현코드가 익숙하지 않아서였는지 꽤나 고생을 했던 문제이다.

문제는 아래와 같다.

https://www.acmicpc.net/problem/17365

17365번: 별다줄

---

의식의 흐름 및 해설

예제입력1의 결과가 왜 109인지 직접 생각해보면 문제 이해에 도움이 된다.

해석하려는 단어가 aaaa 일 때, a는 예제입력1의 세 단어 모두 가능하므로 3*3*3*3=81가지가 있으나, aa의 접두사 aa인 경우도 생각해야 되기 때문에 aa/a/a, a/aa/a, aa/aa 이렇게 3가지 경우 * a로 가능한 3개단어 * a로 가능한 3개단어 = 27가지 경우가 더 있으며, aa/aa 의 1가지 경우까지 총 109개가 나온다.

 

우선 주어지는 모든 단어의 길이의 총합이 1e6 이하이므로, 그리고 특정 단어의 접두사인지 파악하는 문제이므로 트라이로 관리할 수 있어보인다.

트라이에서 자식의 개수를 따로 처리해주기 위해 branch[26] 배열을 추가로 만들어주었다.

그리고 현재까지 가능한 경우의 수 d[i]에서 위에서 말한 a뿐만 아니라 더 긴 aa, aaa의 접두사일 가능성도 존재하기 때문에 branch배열에서의 자식값을 곱한 후, d[i+len]에 더해주었다. 각 단어의 길이는 300 이하이므로 시간초과를 걱정할 필요는 없다.

 

전체 시간복잡도는 O(N*300)이다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
const int MAX = 1000011;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
int N;
ll d[200003];
struct Node {
	bool end;
	int branch[26];	// child의 개수를 구해준다.
	int child[26];	// trie에서 몇 번째 index인지 관리하는 배열
	Node() {
		end = false;
		fill(branch, branch + 26, 0);
		fill(child, child + 26, -1);
	}
};
vector<Node> trie;
string str;
void insert(string& s, int idx, int cur) {
	if (idx >= s.length()) {
		trie[cur].end = true;
		return;
	}
	int x = s[idx] - 'a';
	if (trie[cur].child[x] == -1) {
		trie[cur].child[x] = trie.size();
		trie.push_back(Node());
	}
	trie[cur].branch[x]++;
	insert(s, idx + 1, trie[cur].child[x]);
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N;
	trie.push_back(Node());
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		insert(s, 0, 0);
	}
	cin >> str;
	int x = str[0] - 'a';
	int cur = 0;	// 현재 탐색하고 있는 트라이 index
	for (int i = 0; i < str.length(); i++) {
		x = str[i] - 'a';
		ll num = (i ? d[i - 1] : 1);
		int tmp = trie[0].child[x];	// 접두사 길이가 2 이상인 경우를 더해주자
		for (int j = i + 1; j < str.length(); j++) {
			int tmpx = str[j] - 'a';
			if (tmp >= trie.size() || !trie[tmp].branch[tmpx]) break;
            // 현재까지 가능한 경우의수 * 현재 트라이에서 tmpx자식의 개수
			d[j] += num * trie[tmp].branch[tmpx];
			d[j] %= MOD;
			tmp = trie[tmp].child[tmpx];
		}
		if (i) {
			d[i] += num * trie[0].branch[x];
			d[i] %= MOD;
		}
		else d[i] = trie[0].branch[x];
		if (trie[cur].child[x] == -1)
			cur = 0;
		else
			cur = trie[cur].child[x];
	}
	cout << d[str.length() - 1] << "\n";
}

---

오랜만에 트라이 문제 재밌게 푼 듯하다.

트라이 구현코드를 연결리스트에서 벡터를 이용한 방법으로 바꿔봤는데, 속도 면에서도 만족스럽고, 자식 개수는 내가 추가만 해주면 되니까 생산성 면에서도 만족스러운 듯 하다 ㅎㅎ