[Algorithm]Baekjoon 16500번 :: 문자열 판별

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
string s;
int n;
bool dp[101] = { false }; // dp[i] == s의 0 ~ i-1 번째 인덱스까지, 주어진 단어들로 조합이 가능한가??
unordered_set<string> words;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> s >> n;
    
    for (int i = 0; i < n; ++i)
    {
        string word;
        cin >> word;
 
        words.insert(word);
    }
    
    dp[0] = true; // 공백을 만들 수 있는가?
                  // -> 아무 단어도 선택안하면 만들 수 있다. 
                  // -> 그렇기에 dp[0]에 true.
 
    for (int i = 1; i <= s.size(); ++i) // s의 i-1번째 인덱스까지 단어들을 조합해서 만들 수 있는가?
    {
        for (int j = 0; j < i; ++j)
        {
            if (dp[j] && words.find(s.substr(j, i-j)) != words.end())
            {
                dp[i] = true;
            }
        }
    }
 
    cout << dp[s.size()];
}
 
 

 

일단 Bottom-Up 방식..

특정 문자열 word가 존재하는지의 여부만 알면 되기때문에 unordered_set을 활용한다.

 

dp[i]는 문자열 s의 i-1번째 인덱스까지, 주어진 단어들로 만들 수 있는지에 대한 여부이다.

i가 아니다. i-1이다.

 

dp[0]에는 먼저 true값을 넣는다. 이것은 주어진 단어들로 공백문자열을 만들 수 있는가? 에 대한 질문의 답변을  넣는 것이다. 만들 수 있기 때문에 true값을 넣은것이다. 어떻게? -> 단어들을 하나도 선택하지않으면 공백문자열이 된다.

 

이후 반복문을 돈다. 어떤 단어가 들어있는지 모르니, 전부 체크해줘야 한다.

예시로 하나 설명하자면, 문자열 "abcde" 가 주어졌다고 가정해보자.

abcde가 만들어지는지 체크하기위한 검사로, abcd 가 이전에 만들어질 수 있는지 체크해보고 이후 e가 단어들중에 있는지 찾으면 된다. (이건 검사들 중 하나일 뿐이다)

혹은 abc가 유효한 문자열인지 체크한 후, de가 단어들 사이에 있는지 찾는다.

혹은 ab가 유효한지 체크한 후, cde가 단어들 사이에 있는지 체크하면 된다.