05.14. 문자열 판별 [Dynamic Programming][백준 16500]

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

16500번: 문자열 판별

 

Algorithm classification : Dynamic Programming, String

 

05.14.1. Problem

Given a string S consisting of lowercase letters and a list of words A, write a program to find out whether S can be formed by concatenating one or more strings in A without spaces. A word in A can be used multiple times.

 

05.14.2. Input limit

The first line is given a string S of length 100 or less. In the second line, the number of strings in A is given N (1 ≤ N ≤ 100). From the third line to the N lines, the word contained in A is given, one per line. The character string included in A consists only of lowercase letters, and the length does not exceed 100.

 

05.14.3. Output

Outputs 1 if S can be made from the string included in A, and 0 if not.

 

05.14.4. Solution

문자열에 대한 기초가 있어야 하긴 합니다. 앞에서부터 대조하여 남은 문자열을 계속 만들 수 있는지 구하면 됩니다. 문자열의 길이 최대값을 M이라 하면 O(NM^2) 시간복잡도를 가집니다. 조금 무식한 CODE는 아래와 같습니다.

void cal(int index){
	//printf("%d %d\n", index, size_ans);
	
	int i, j, k;
	char c[100] = {0};
	if(size_ans == index) check = true;
	for(i = 0; i < n; i++){
		
		k = strlen(a[i]);
		
		if(k + index <= size_ans){
			for(j = index; j < index + k; j++){
				c[j-index] = ans[j];
			}
			for(j = index + k; j < 100; j++){	
				c[j] = 0;
			}
			
			//printf("%s %s\n", a[i], c);
			if(a[i][0] != c[0]) continue;
			if(strcmp(a[i], c) == 0){
				cal(index + k);
			}
		}
	}
	return;
}

int main()
{
	int i;
	
	scanf("%s", ans);
	size_ans = strlen(ans);
	
	scanf("%d", &n);
	for(i = 0; i < n; i++){
		scanf("%s", a[i]);		
	}
	cal(0);
	printf("%d", check ? 1 : 0);
	
	
	return 0;
}

조금 우아하게 작성한 CODE는 아래와 같습니다.

	for (i = s.length() - 1; i >= 0; i--) {
		for (j = 0; j <= N; j++) {
			if (s.find(a[j], i) == i && dp[i + a[j].length()] == 1) {
				dp[i] = 1;
				break;
			}
			else {
				dp[i] = 0;
			}
		}
	}

몇 개의 도움이 될만한 test case를 남겨두겠습니다.

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
4
aaa
aaaa
aaaaa
aba

>> 0

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacaaab
4
aba
a
aa
ac

>> 0

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
2
aa
aaaa

>> 0

abababababababababababababababababababababababababababababababababababababababababababababababababc
10
abababababababababa
ababababababababa
abababababababa
ababababababa
abababababa
ababababa
abababa
ababa
aba
b

>> 0

 

 

조금 더 어려운 문제를 추천해드리자면 https://kunkunwoo.tistory.com/80

알고스팟_ 와일드 카드_ 종만북_DP

를 참고하시면 좋을 듯 합니다. 저는 이 문서의 code를 이해하는데 상당한 시간이 들었습니다.