[백준] 16500 문자열 판별

문제 링크

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

사용 알고리즘

• DP

풀이

dp 리스트에 `해당 인덱스까지 words 배열에 존재하는 단어들로 표현할 수 있는가`를 저장한다.

초기값인 dp[0]은 1로 두고 s의 인덱스마다 dp[i]가 1일 경우 words 배열에 존재하는 단어들을 체크해서 `s[i:i+len(w)] == w`라면 dp[i+len(w)]를 1로 저장한다.

 

dp[i]까지는 이미 이전에 words 배열에 존재하는 단어들로 만들 수 있음을 확인했기 때문에,

우리는 그 후의 s의 부분 문자열에 대해 words 배열에 존재하는 단어들로 s의 부분 문자열과 일치하는 단어들이 있는지 판별해야 하기 때문이다.

예시

Input

abcefg
3
abc
efg
abce

 

초기 상태

index	0	1	2	3	4	5	6
s	a	b	c	e	f	g
dp	1	0	0	0	0	0	0

 

i == 0

"abc", "abce"가 일치함으로 각각 `i + len(w)`인 3, 5번 인덱스를 1로 설정한다.
> 이로 인해 2 또는 4번 인덱스까지는 일치하는 단어가 있음을 알 수 있다.

index	0	1	2	3	4	5	6
s	a	b	c	e	f	g
dp	1	0	0	1	0	1	0

 

i == 3

"efg"가 일치함으로 `i + len(w)`인 6번 인덱스를 1로 설정한다.
> 이로 인해 6번 인덱스까지 일치하는 단어가 있음을 알 수 있다.

index	0	1	2	3	4	5	6
s	a	b	c	e	f	g
dp	1	0	0	0	0	0	0
	1	0	0	1	0	1	0
	1	0	0	1	0	1	1

코드

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

s = input()
words = [input() for _ in range(int(input()))]
dp = [0] * (len(s) + 1)
dp[0] = 1

for i in range(len(s)):
    if not dp[i]: continue

    for w in words:
        if s[i:i+len(w)] == w:
            dp[i + len(w)] = 1

print(dp[-1])