[백준] 16500 - 문자열 판별

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

16500번: 문자열 판별

 

이 문제는 처음 봤을 때는 완전 탐색 문제일 줄 알았다.

하지만 다음과 같은 입력이 들어온다면?

 

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa(a가 홀수개)
8
aa
aaaa
aaaaaa
aaaaaaaaaa
aaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

 

이런 식으로 입력이 들어온다면 답은 0이지만, 완전 탐색 시 분명히 시간 초과를 맞게 될 것이다.

 

그럼 어떻게 풀어야 할까?

잘 생각해보면, "공백 없이 붙여서"라는 부분을 볼 수 있는데, 즉 문자열 S의 어떤 index까지 만들 수 있으면, 그 이전에 과정은 중요치 않다는 것이다. 따라서 이 문제는 dp로 풀 수 있다.

 

#include <iostream>
#include <vector>
using namespace std;

string s;
string v[100];
int n, dp[100];

int main() {
    cin >> s >> n;

    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < n; j++) {
            int len = v[j].length();
            if ((i == 0 || dp[i - 1]) && i + len <= s.length() &&
                s.substr(i, len) == v[j]) {
                dp[i + len - 1] = 1;
            }
        }
    }
    cout << dp[s.length() - 1];
}