문제링크: https://programmers.co.kr/learn/courses/30/lessons/12983

1. 아이디어💡

1.1. 문제분석

• 단어 조각들을 이용해서 주어진 타겟 단어를 완성해야한다.
• 단어 조각을 최소로 사용해야한다.

1.2. 해결 방법

다이나믹 프로그래밍

1. f(n)을 t 문자열의 n번째 문자까지를 단어 조각으로 만들 수 있을 때 필요한 최소의 단어 조각 수를 반환할때 점화식은 다음과 같다.

f(n) = min([f(n-5), f(n-4), f(n-3), f(n-2), f(n-1)]) + 1

2. f(n)을 구할 때 f(n)이 가능한지 먼저 검사해야 한다. 입력이 다음과 같이 주어 졌을 때

strs = ["ba","na","n","a"]
t = "banana"

3. "b"를 완성할 수 없는 단어조각은 없지만 "ba"를 완성할 수 있는 단어조각이 있으므로 f(1)은 1이 된다. 그리고 그다음 "n"을 완성할 수 있으므로 f(2)는 2가 되고 f(3)은 "na" 또는 "a"을 통해서 완성될 수 있고 f(1)이 f(2) 보다 작으므로 f(3) = f(1) + 1 = 3 이 된다.

2. 코드

from collections import deque

def solution(strs, t):
    strs = set(strs)
    mem = [len(t)+1] * len(t) # 문자열의 n번째 문자까지 필요한 최소 단어 조각의 수 (메모이제이션)
    q = deque()
    q.append((0, 0)) # (n번째 문자의 인덱스, 사용한 단어개수)
    while q:
        counts = q.popleft()
        scr = counts[1] + 1 # 단어 한개 추가
        end_i = counts[0] + 5 if len(t) - counts[0] >= 5 else len(t)
        for i in range(counts[0], end_i):
            if t[counts[0]:i + 1] in strs and mem[i] > scr:
                if i + 1 == len(t): # t의 끝에 도착했다면 사용한 최소 단어개수 반환
                    return scr
                q.append((i + 1, scr))
                mem[i] = scr
    return -1