백준 16500: 문자열 판별

문제 요약

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

문제 분류

• 다이나믹 프로그래밍
• 문자열

문제 풀이

이 문제는 이전에 탑다운으로 푼 경험이 있어 이번에는 바텀업 방식으로 구현했다.

dp[i]는 str의 i번째부터 끝까지의 문자열이 v[j] (0 <= j < n)에 있는지의 여부이다.

이때 i는 str의 끝 문자부터 0으로 내려온다.

예를 들어 dp[8]은 'c'문자부터 문자열의 끝인 't'까지, 즉 "contest"와 일치하는 v[j]의 시작이 8번 인덱스인지 검사한다. v[1]의 문자열이 "contest"여서 일치하므로 dp[8]에는 dp[8 + 7("contest"의 길이)]를 저장한다.

이는 옳은 문자열이 있어도 반드시 true가 되는 것이 아닌, "contest"이후의 문자열이 옳아야 true가 되기 때문이다.

dp[1]은 문자 'o'부터 문자열의 끝인 't'까지, 즉 "oftwarecontest"와 일치하는 v[j]의 시작이 1번 인덱스인지 검사한다. v[0]의 문자열이 "software"이어서 일치하는 것이 없으므로 이는 false가 된다.

dp[0]은 첫 문자 's'부터 끝인 't'까지, 즉 "softwarecontest"와 일치하는 v[j]의 시작이 0번 인덱스인지 검사한다. v[0]의 문자열이 "software" 이어서 일치하므로, dp[0] = dp[0 + 8("software"의 길이)가 된다. 즉, dp[8]이 true라면 str[8]이후의 문자열은 v[]의 문자열로 만들 수 있다는 의미이므로 dp[0]도 true가 될 것이다.

​

즉, (str.find(v[j], i) == i)라면, dp[i] = dp[i + v[j].length()]가 될것이다. 그러나, 이미 dp[i] 가 true라면, 그 일치여부와 관계없이 true가 되므로 dp[i] = dp[i] || dp[i + v[j].length()] 가 된다.

이제 i를 str.length()-1부터 0까지, j를 0부터 n번 돌리면 된다.

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
str	s	o	f	t	w	a	r	e	c	o	n	t	e	s	t
dp	1	0	0	0	0	0	0	0	1	0	0	0	0	0	0	1

풀이 코드

• 바텀업(Bottom-up) 방식

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

bool dp[100];
string v[101];

int main()
{
	int n;
	string s, input;
	cin >> s;
	cin >> n;
	bool res = false;

	for (int i = 0; i < n; i++)
		cin >> v[i];
	int size = s.length();
	dp[size] = true;
	for (int i = size; i >= 0; i--) {
		for (int j = 0; j < n; j++) {
			if (size < v[j].length() + i) continue;
			if (s.find(v[j], i) == i)
				dp[i] = dp[i] || dp[i + v[j].length()];
		}
	}
	cout << dp[0];
	return 0;
}

• 탑다운(Top-down) 방식

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

string S, ary[101];
int n, dp[101];

bool word(int k)
{
	if (k == S.length()) return true;
	int& res = dp[k];

	if (res != -1) return res;
	res = 0;

	for (int i = 0; i < n; i++) {
		if (S.length() < ary[i].length() + k) continue;
		if (S.find(ary[i], k) == k)
			res = res || word(k + ary[i].length());
	}
	return res;
}

int main() {

	cin >> S;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> ary[i];
	memset(dp, -1, sizeof(dp));

	cout << word(0);
	return 0;
}