[Programmers] P12983 단어 퍼즐

[Programmers] P12983 단어 퍼즐

Question

Language: Python

Difficulty: Gold 4~5

해당 문제는 처음 부터 문자열을 추가하면서 만들어가는 과정을 취하면 시간 내에 풀이를 할 수 없다.

이 문제는 LIS에서 착안된 DP 유형의 문제이다. 문자열에 조합에 사용되는 단어 조각이 5자리 이내라는 부분을 유심히 봐야한다.

i를 기준으로 왼쪽으로 1~5 자리에 해당하는 문자열을 검사해서, 해당 문자열(dp[s:i])이 strs 배열에 있는 경우들 중에서 dp[s]의 값이 최소값인 경우를 선택해서 1을 더해주는 방식으로 dp를 초기화한다. 즉, 이전 자리에 추가된 문자열을 비교해서 현재의 값을 최신화하는 방식이다.

Solution

from math import inf   
def solution(strs, t):
    length=len(t)
    
    dp=[inf]*(length+1)
    dp[0]=0
    strs=set(strs)
    
    for i in range(1,length+1):
        for j in range(1,6):
            s=i-j
            s=max(0,i-j)
            
            if t[s:i] in strs:
                dp[i]=min(dp[i],dp[s]+1)
                
    return dp[length] if dp[length] != inf else -1