[프로그래머스] 단어 퍼즐(Python)

https://programmers.co.kr/learn/courses/30/lessons/12983

코딩테스트 연습 - 단어 퍼즐

dp 활용 문제다. 처음에 그리디 + dfs로 풀었는데 시간 초과가 났다.

 

dp를 생각하긴 했는데 dp에 익숙하지 않아서 다른 사람 풀이를 참고했다.

 

dp를 설계할 때 일반적으로 원하는 답을 설정하면 구하기 쉽다.

 

이 문제는 각 위치에서 단어조각 개수의 최솟값을 return 하는 문제이므로

dp를 각 위치에서의 최소 단어조각 개수로 설정해주고 문제를 풀면 된다.

 

단어 조각의 최대 수는 5개이므로 이를 참고하여 작성한다.

 

import math
def solution(strs, t):
    INF = math.inf
    dp = [INF for _ in range(len(t)+1)]
    dp[0] = 0
    for i in range(1,len(t)+1):
        j = 0 if i < 5 else i - 5
        while j < i:
            if dp[j] + 1 < dp[i] and t[j:i] in strs:
                dp[i] = dp[j]+1
            j +=1
    return dp[len(t)] if dp[len(t)] != INF else -1