# [Gold V] 문자열 판별 [문제링크](https://www.acmicpc.net/problem/16500) ## 문제 설명 <p>알파벳 소문자로 이루어진 문자열 S와 단어 목록 A가 주어졌을 때, S를 A에 포함된 문자열을 한 개 이상 공백없이 붙여서 만들 수 있는지 없는지 구하는 프로그램을 작성하시오. A에 포함된 단어를 여러 번 사용할 수 있다.</p> ## 입력 <p>첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.</p> ## 출력 <p>A에 포함된 문자열로 S를 만들 수 있으면 1, 없으면 0을 출력한다.</p> ## 풀이 #### 이 문제는 n개의 문자열 A를 중복해서 잘 배치하여 문자열 S를 만들 수 있는지를 물어보는 문제입니다. #### n이 최대 100이고, 문자열의 길이도 100 이하여서 브루트포스로도 잘 풀릴 것 같습니다. #### 하지만 문자열을 붙이는 과정을 쉽게 dp로 나타낼 수 있습니다. 이때 dp[i]를 "i번째 문자까지를 A로 만들 수 있는가"로 정의하고 풀면 쉽게 풀립니다. ``` c++ #include<bits/stdc++.h> using namespace std; int n; string s; vector<string> a(100); int match(int startIdx, int aIdx) { for(int i=0;i<a[aIdx].length();i++) { if(s.length()<=startIdx+i || s[startIdx+i] != a[aIdx][i]) { return -1; } } return startIdx+a[aIdx].length(); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> s >> n; for(int i=0;i<n;i++) cin >> a[i]; // dp[i] : i번째 문자까지 완성 가능 vector<bool> dp(s.length()+1); dp[0]=true; for(int i=0;i<s.length();i++) { if(dp[i]) { for(int j=0;j<n;j++) { int ret = match(i, j); if(ret!=-1) dp[ret]=true; } } } cout << dp[s.length()]; } ```