[백준] 문자열 판별

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

16500번: 문자열 판별

 

A에 포함된 문자열을 한 개 이상 붙일 수 있으므로 dp[index] 가 1이면 이미 재귀함수로 A의 문자열로 S를 만들 수 있는지 확인하고 있으므로 무시해도 된다.

 

DFS 알고리즘으로 

S = 'softwarecontest'

A = ['software', 'contest'] 라면

1) index = 0 (dp[0] = 1) : softwarecontest(= S[0:]) 와 software

  1 - 1) index = 0 + len('software') = 8 (dp[8] = 1) : contest(= S[8:]) 와 contest

  1 - 2) index = 8 + len('contest') = 15 가 len(S) 랑 일치하는 경우 dp[-1] = 1

2) index = 0 : softwarecontest 와 contest, index = 0 에서 일치하지 않으므로 break

 

dp[-1] 을 반환한다.

 

import sys

def rf(index):
    if index == len(S):
        dp[-1] = 1
        return
    else:
        if dp[index] != 1:
            dp[index] = 1
            
            for i in range(N):
                if len(S[index:]) >= len(A[i]):
                    for j in range(len(A[i])):
                        if S[index+j] != A[i][j]:
                            t = False
                            break
                            
                    else:
                        rf(index + len(A[i]))
                    
S = sys.stdin.readline().strip()
N = int(sys.stdin.readline())
A = []

for i in range(N):
    A.append(sys.stdin.readline().strip())

dp = [0] * (len(S) + 1)
rf(0)

print(dp[-1])