beakjoon 16500: 문자열 판별

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

16500번: 문자열 판별

초기에 문제를 읽고 백트래킹으로 구현을 하면 되겠다 싶어서 백트래킹과 dfs를 섞어서 구현을 하였지만 시간초과가 났다.

s = list(input())
n = int(input())
arr = []
for _ in range(n):
    arr.append(list(input()))


result = []
def dfs(level,word):
    if level == len(s):
        if s == word:
            result.append(1)
            return
        else:
            result.append(0)
            return
    if 1 in result:
        return

    if level > len(s):
        return

    for i in range(n):
        dfs(level+len(arr[i]),word+arr[i])
dfs(0,[])

if 1 in result:
    print(1)
else:
    print(0)

시간초과가 난 이유(반례)를 홀로 생각을 해보니.. 만약 길이가 100인 문자열을 입력받았다고 치자.

 

조합을 위한 단어들이 100개가 있는데 그 단어들이 전부 길이가 1인 단어라면 백트래킹을 이용해도 엄청난 시간이 걸릴것이다.

 

그래서 애초에 처음 index부터 맞는 조합을 맞췄다면 그 다음 index로 넘어가는 dp적인 개념이 필요하겠구나 생각했다..!

 

허나 dp는 아직 나에겐 많이 어려운 개념.. 구글링을 통해 다른분의 코드를 인용하여 결국 정답을 제출하였다 허허

s = list(input())
n = int(input())
arr = []
dp_arr = [0] * 101 #체크된 부분부터 탐색을 해야하므로 필요
for _ in range(n):
    arr.append(list(input()))
result = 0

def dp(idx):
    global result
    if idx == len(s): # idx가 입력받은 문자열과 같다면 return
        result = 1
        return
    if dp_arr[idx] ==1: 
        return
    dp_arr[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
                    break
            else:
                dp(idx+len(arr[i])) # 단어조합에 성공하였다면 다음 idx부터 단어를 찾는다
    return

dp(0)
print(result)