[C++]백준 - 16500번 문제

16500번: 문자열 판별 (acmicpc.net)

16500번: 문자열 판별

 

16500번 : 문자열 판별

---

알파벳 소문자로 이루어진 문자열 S와 단어 목록 A가 주어졌을 때, S를 A에 포함된 문자열을 한 개 이상 공백없이 붙여서 만들 수 있는지 없는지 구하는 프로그램을 작성하시오. A에 포함된 단어를 여러 번 사용할 수 있다.

 

입력

---

첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.

 

 

출력

---

A에 포함된 문자열로 S를 만들 수 있으면 1, 없으면 0을 출력한다.

 

 

 

---

 

생각해 볼 점

---

 

문자열 검사 문제입니다.

 

일단, 트라이로 풀면 동작은 합니다. 다만, 트라이로 푼 경우 시간 초과를 피할 수 없습니다.

 

그러므로 DP를 활용하여 풀었습니다.

 

DP[i] = i 지점에서 문자열 S를 만들 수 있는가?

 

DP[i] = 0 -> 만들 수 없다.

DP[i] = 1 -> 만들 수 있다.

DP[i] = -1 -> 검사하지 않아 모른다.

 

예를 들어, S가 softwarecontest이고

 

A[2] = {software, contest}라고 합시다.

 

문자열을 담는 벡터 V를 하나 생성해서, 

 

A의 문자열을 입력 받을 때, 알파벳 첫 문자의 index에 해당하는 위치에 문자열을 담습니다.

 

그러면, V[18] = {"software"}, V[2] = {"contest"}

 

와 같이 문자열이 담깁니다.

 

이제, S를 검사합니다.

 

S의 0번째 index부터 검사를 시작할 것이므로, DP[0]을 구하는 과정과 같습니다.

 

S의 첫 글자는 s이고, s의 index는 18입니다.

 

V[18]에 존재하는 모든 문자열과 S를 비교합니다.

 

S의 문자열과 software는 일치하므로, software의 글자 수 = 8만큼 index를 증가시켜 DP[8]을 구합니다.

 

DP[8]도 같은 방식으로 구하면, contest = contest로 글자가 모두 일치하고, 알고리즘이 종료되어 1을 반환합니다.

 

 

한번이라도 1이 반환된 경우 나머지 문자열을 더 비교할 필요가 없으니 1을 반환후 종료합니다.

 

 

 

 

코드

---

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string S;
int S_len;
vector<string> inputs[26];
int* dp;

int solution(int current)
{
	if (S_len == current) return 1;
	if (S_len < current) return 0;
	if (dp[current] != -1) return dp[current];

	int result = 0;
	for (string s : inputs[S[current] - 97])
	{
		int s_len = s.size();
		if (S_len - current < s_len) continue;
		bool is_continue = false;
		for (int i = 0; i < s_len; i++)
		{
			if (S[current + i] == s[i]) continue;
			is_continue = true;
			break;
		}
		if (is_continue) continue;

		if (result += solution(current + s_len)) break;
	}
	return dp[current] = result;
}


int main()
{
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);
	int N;
	cin >> S >> N;
	
	S_len = S.size();
	dp = new int[S_len];
	fill_n(dp, S_len, -1);
	while (N--)
	{
		string input;
		cin >> input;
		inputs[input[0] - 97].push_back(input);
	}
	printf("%d", solution(0));

	delete[] dp;
	return 0;
}

 

그 외

---