간단한 1차원 DP문제. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

/*
1. strs라는 문자열 배열과 t라는 문자열이 주어질 때, strs 문자열 배열의 원소들로 t라는
   문자열을 만드는 경우의 수가 얼마나 되는지를 구하는 문제. 
   (단, strs 배열의 원소의 길이는 최대 5.)
   
   
2. dp[i] : strs 문자열 배열을 이용해 t 문자열의 i번 인덱스까지 만드는 경우의 수
   로 dp 배열을 정의한 후, 다음과 같은 점화식을 통해 DP 문제로 풀 수 있다.
   
   dp[i] = (1) dp[i-j-1] + 1 (t의 i-j번 인덱스부터 i번 인덱스까지의 부분문자열이
   				strs 배열의 원소인 경우. 단, j는 0부터 4까지 수 중 최솟값.)
                              
           (2) 0             (t의 i번 인덱스부터 i번 인덱스까지의 부분문자열,
           			  i-1번 인덱스부터 i번 인덱스까지의 부분문자열,
                                  ...,
                    		  i-4번 인덱스부터 i번 인덱스까지의 부분문자열이 모두
           			  strs 배열의 원소가 아닌 경우)


3. 이 문제에서 DP 알고리즘을 수행할 때 시간복잡도가 커질 수 있는 부분은
   't의 i-j번 인덱스부터 i번 인덱스까지의 부분문자열이 strs 배열의 원소인지 아닌지'
   를 찾는 과정이다. 순차적으로 탐색할 경우 O(n)의 시간복잡도를 갖는다.
   C++의 STL에서 지원하는 set 자료구조는 내부구조가 완전 이진 트리로 구현되어 있어,
   특정 원소가 set에 저장되어 있는지를 O(logn) 시간 안에 판별할 수 있다.
   이 문제에서는 이 부분에 주목하여 C++ STL의 set 자료구조를 적극 사용하였다.
   또한, set 자료구조를 사용해 구현하면 for문의 사용을 줄여 보다 직관적으로 
   코드를 쓸 수 있다는 이점도 있다.
*/

#include <string>
#include <vector>
#include <set>
using namespace std;
set<string> strs_set;
int dp[20000];

int solution(vector<string> strs, string t)
{
    for (auto str: strs)
        strs_set.insert(str);
    for (int i=0; i<t.length(); i++)
        for (int j=0; j<5 && i-j >= 0; j++)
            if (strs_set.find(t.substr(i-j, j+1)) != strs_set.end())
                if (i-j == 0)
                    dp[i] = 1;
                else if ((dp[i] == 0 || dp[i] > dp[i-j-1] + 1) && dp[i-j-1] != 0)
                    dp[i] = dp[i-j-1] + 1;

    return (dp[t.length()-1] == 0) ? -1 : dp[t.length()-1];
}