문제

알파벳 소문자로 이루어진 문자열 S와 단어 목록 A가 주어졌을 때, S를 A에 포함된 문자열을 한 개 이상 공백없이 붙여서 만들 수 있는지 없는지 구하는 프로그램을 작성하시오. A에 포함된 단어를 여러 번 사용할 수 있다.

입력

첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.

출력

A에 포함된 문자열로 S를 만들 수 있으면 1, 없으면 0을 출력한다.

예제 입력 1

softwarecontest
2
software
contest

예제 출력 1

1

나의 풀이

import sys
input = sys.stdin.readline
S = str(input().rstrip())
S_list = list(S)

N = int(input())
dp = [0] * (len(S_list) + 1) #단어의 길이 (+ 1)만큼 
dp[0] = 1

words = []
for _ in range(N):
    word = str(input().rstrip())
    words.append(word)

for i in range(len(S_list) + 1):
    for word in words:
        word_len = len(word)
        #i가 비교하고자 하는 단어보다 길거나 같고, i 직전까지의 단어가 이미 비교가 되었으며(=dp == 1이며), slice 한 부분이 word와 똑같다면
        if i >= word_len and dp[i - word_len] == 1 and S_list[i - word_len:i] == list(word):
            dp[i] = 1
            
#dp의 마지막 배열의 값이 1이라면
if dp[len(S_list)]:
    print(1)
else:
    print(0)

풀이 과정

예제에 나온 문제만을 해결하는 코드는 간단하게 짤 수 있지만, 문제에는 여러 함정 케이스가 있는지 푸는 게 쉽지 않았다.
문자열 S를 리스트로 만들고, 이어서 제시되는 단어들도 words로 만든 후에 다음과 같은 조건을 통과한 단어들이 S를 완성하는지 판별하면 된다.
반복문에서 i가 비교하고자 하는 단어의 길이(len(word))보다 길거나 같고, i 직전까지의 단어가 이미 비교가 되었으며(=dp[i - word_len] == 1이며), 비교를 위해 slice 한 부분이 word와 똑같다면 dp[i]를 1로 바꾼다.
이 과정이 반복되어 문자열 s가 제대로 채워졌다면 dp[len(S_list)] 역시 1이 되었을 것이다.