백준 16500번: 문자열 판별

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

16500번: 문자열 판별

S를 이룰 각 문자열 A_i와 그 길이 A_i_size에 대해, S에서 k부터 시작하는 A_i를 찾고 S[0:k]를 주어진 문자열을 이용해 만들 수 있다면, S[0:k+A_i_size] 역시 만들 수 있다. 이 과정을 k가 0일 때부터 S의 길이까지 반복한다면 S를 주어진 A의 집합만으로 만들 수 있는지 확인할 수 있다.

#include <iostream>
#include <string>

using namespace std;

#define MAX_LEN 100

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // dp[l]: S.substr(0, l)을 A의 집합만으로 완성시킬 수 있다면 true
    //        이 때 S.substr(0, 0)은 어떤 경우에서도 만들 수 있다고 가정
    bool dp[MAX_LEN + 1] = { true, };
    // N: A의 원소 개수, len: S의 길이 (S.size()의 호출 최소화)
    // idx: dp의 이전 값을 확인할 때 사용할 인덱스
    int N, len, idx;
    // S: A의 부분집합으로 완성시킬 문자열
    // A: S를 완성시키기 위해 주어진 문자열의 집합
    string S, A[MAX_LEN];

    // 주어진 조건을 입력받은 뒤
    cin >> S >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    // S의 크기를 변수에 별도로 저장
    len = S.size();

    // dp를 활용해 S를 만들 수 있는지 검토
    for (int l = 1; l <= len; l++) for (int i = 0; i < N; i++) {
        // A[i]보다 작은 S의 부분 문자열은 검토하지 않는다
        if (l < A[i].size()) continue;

        // 부분 문자열에서 A[i]를 제거한 만큼의 길이
        idx = l - A[i].size();
        // 부분 문자열의 마지막에 A[i]가 존재하고,
        // 또 마지막의 A[i]를 제거한 부분 문자열을 만들 수 있다면
        // 길이가 l 부분 문자열을 만들 수 있다고 간주
        if (dp[idx] && S.substr(idx, A[i].size()) == A[i]) dp[l] = true;
    }

    // 길이가 len인 부분 문자열, 즉 전체 문자열을 만들 수 있는지 여부를 출력
    cout << (int)dp[len] << '\n';

    return 0;
}