[백준 16500] 문자열 판별 (C++)

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

문제

---

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

입력

---

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

 

출력

---

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

 

문제 풀이

---

dp 문제.

 

dp[i]가 dp[i-1]번째 인덱스까지의 문자를 만들 수 있는지의 여부를 저장한다고 정하자. dp[i]가 true이며 문자열 S의 i번째 인덱스부터 j(단, j는 단어 목록 A에 존재하는 문자열)가 포함되어 있다면, dp[i + j.length()] 역시 true가 된다.

이를 이용하여 인덱스 0부터 M까지 탐색하며 dp[0]부터 가능한지 채워나가자. dp[0]는 base이므로 0번 인덱스에서 시작하는 j가 있는지 찾아낸다. 만약 존재한다면 dp[j.length()]를 true로 변경한다.

dp[i]가 false라면 i번째 인덱스 이전까지의 문자열을 어떤 경우든 만들 수 없으므로 탐색할 필요가 없다. dp[i]가 true라면 i번째 인덱스 이전까지의 문자열을 만들 수 있는 경우이고, 이제 j가 있는지 확인하면 된다. dp[0]과 마찬가지로 존재한다면 dp[i + j.length()]를 true로 변경하면 된다.

 

만들 수 있는 경우라면 dp[M]이 true인 경우이므로 이 때 1을 출력해주면 되고, 아니라면 0을 출력해주면 된다.

 

 

아래는 코드.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	string str;
	int N, M;
	cin >> str;
	cin >> N;
	M = str.length();
	bool* dp = new bool[M + 1];
	string* inputs = new string[N];
	for (int i = 0; i < M + 1; i++)
	{
		dp[i] = false;
	}
	for (int i = 0; i < N; i++)
	{
		cin >> inputs[i];
	}
	for (int index = 0; index < M + 1; index++)
	{
		if (index == 0 || dp[index] == true)
		{
			for (int j = 0; j < N; j++)
			{
				int findIndex = str.find(inputs[j], index);
				if (findIndex == index)
				{
					dp[index + inputs[j].length()] = true;
				}
			}
		}
	}
	if (dp[M] == true)
	{
		cout << 1 << "\n";
	}
	else
	{
		cout << 0 << "\n";
	}
	return 0;
}