BOJ - 16500 - 문자열 판별

import sys

def solve(idx, ret, dp, arr, S):
    if idx == len(S):
        ret[0] = 1
        return

    if dp[idx]:
        return

    dp[idx] = 1
    for i in range(len(arr)):
        if len(S[idx:]) >= len(arr[i]):
            for j in range(len(arr[i])):
                if arr[i][j] != S[idx + j]:
                    break
            else:
                solve(idx + len(arr[i]), ret, dp, arr, S)
    return

def solution():
    S = sys.stdin.readline().strip()
    N = int(sys.stdin.readline())
    arr = []
    dp = [0] * 101
    for _ in range(N):
        arr.append(sys.stdin.readline().strip())

    ret = [0]
    solve(0, ret, dp, arr, S)
    print(ret[0])
solution()

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