[1일 1알고] G5 16500 문자열 판별

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

 

간단한 dp문제입니다.

 

여느 dp문제가 그렇듯이 풀이 아이디어가 떠오르는 지에 따라 해결 시간이 많이 차이가 나는 느낌입니다.

 

이번 문제는 문자열 S를 단어목록 A를 통해 공백없이 붙여서 만들 수 있는지 여부를 확인하는 문제입니다.

 

예를 들어 S = "ABCD"이고, 주어진 A  = {"A", "AB", "BCD", "ABCE"} 라면 A와 BCD를 조합해서 S를 만들 수 있고 답은 1이 됩니다.

 

또한 조건을 보면 S의 길이는 100이하이며, A의 문자열 개수도 100이하이고, A에 포함되는 개별 문자열의 길이도 100을 넘지 않기 때문에 시간 제한 자체는 넉넉해 보입니다.

---

일단 완성을 해야하고, 공백없이 붙여서 만들어야하기 때문에 앞부터 차근차근 해결해나가면 될 것 같습니다.

다만 앞에 무슨 문자열을 붙여야 완성이 될지 모르기 때문에 모든 경우를 고려해야할 것입니다.

 

다행인 것은 문제의 조건에 A에 포함된 단어를 여러 번 사용할 수 있다고 되어있는 점입니다. 그리고 문제는 완성이 가능한지만 물어보기 때문에 더 간단합니다.

---

해당 지점까지 완성이 가능한가? 여부를 bool vector로 표현합니다.

    vector<bool> dp(S.size() + 1, false);
    dp[0] = true;

    for (int idx = 0; idx < S.size(); ++idx)
    {
        for (int i = 0; i < N; ++i)
        {
            if (dp[idx])
            {
                int size = A[i].size();

                if (idx + size > (int)S.size())
                    continue;

                bool flag = false;
                for (int j = 0; j < size; ++j)
                {
                    if (S[idx + j] != A[i][j])
                    {
                        flag = true;
                        break;
                    }
                }
                if (!flag)
                    dp[idx + size] = true;
            }
        }
    }

 코드로 표현하면 위와 같습니다.

현재 이전까지 문자열이 완성되어있다면(dp[idx] == true) 다음 문자열을 이어볼 수 있습니다.

만약에 이어진다면, 해당지점까지 문자열이 완성되었다고 체크합니다. 이를 반복해 문자열의 마지막 글자 시점에서도 완성이 되어있다면 답이 1이 되는 것입니다.