문제 보기 · Level 4 · 2017 팁스타운 · 정답률 27% · 푼 사람 1,617명 (2026-09-30 기준)1

문제

단어 조각들(각각 무한히 있음)을 이어 붙여 문장 t를 만든다. 필요한 조각 수의 최솟값을 돌려준다. 만들 수 없으면 −1이다.

  • 조각 1 ~ 100개(중복 없음), 조각 길이 1 ~ 5
  • t 길이 1 ~ 20,000, 소문자만

풀이

막히면 한 단계씩 펼친다.

필요한 개념

동적 계획법: “앞 i글자를 만드는 최소 조각 수”를 앞에서부터 채운다. 마지막 조각의 길이(1 ~ 5)만 따지면 된다.

1단계 · 작은 예로 손으로 풀기

조각 [ba, na, n, a], 문장 banana

  • ba + na + na = 3개
  • ba + na + n + a = 4개

가장 적은 것은 3이다. 마지막 조각이 na라면 앞 “bana”를 가장 적게 만든 수 + 1이고, 마지막 조각이 a라면 앞 “banan”을 가장 적게 만든 수 + 1이다. 마지막 조각마다 앞부분의 답을 쓰면 된다.

2단계 · 가장 단순한 방법과 그 속도

조각을 앞에서부터 붙여 보는 모든 경우를 다 보면, 같은 위치에 여러 방법으로 도착하는 일이 되풀이되어 경우가 폭발한다(길이 20,000).

3단계 · 핵심 아이디어
  • 상태: dp[i] = t의 앞 i글자를 만드는 최소 조각 수. dp[0] = 0(빈 문장).
  • 점화식: 마지막 조각의 길이를 L(1 ~ 5)이라 하면, t[i − L:i]가 조각이면 dp[i]는 dp[i − L] + 1이 될 수 있다. 그중 가장 작은 값이다.
  • 확인: 조각을 집합에 넣어 두면 t[i − L:i]가 조각인지 바로 본다.
  • 답은 dp[len(t)], 무한대면 −1.
4단계 · 코드 흐름
  1. 조각을 집합으로 만든다. dp = [0, ∞, ∞, …].
  2. i = 1 ~ len(t), L = 1 ~ 5마다: L ≤ i이고 t[i − L:i]가 조각이면 dp[i] = min(dp[i], dp[i − L] + 1).
  3. dp[len(t)]를 돌려준다(무한대면 −1).
5단계 · 파이썬 코드 
def solution(strs, t):
    pieces = set(strs)
    INF = float("inf")
    dp = [0] + [INF] * len(t)                 # dp[i]: 앞 i글자의 최소 조각 수
    for i in range(1, len(t) + 1):
        for L in range(1, 6):                 # 마지막 조각 길이
            if L <= i and dp[i - L] + 1 < dp[i] and t[i - L:i] in pieces:
                dp[i] = dp[i - L] + 1
    return dp[len(t)] if dp[len(t)] != INF else -1
  • t[i - L:i]: i번째 글자 앞의 L글자, 곧 마지막 조각 후보다.
  • 조건 순서를 dp[i - L] + 1 < dp[i]부터 두면 줄일 수 없을 때 문자열 자르기를 건너뛰어 조금 빠르다.
6단계 · 실행 추적

조각 [app, ap, p, l, e, ple, pp], 문장 apple

i 앞 i글자 마지막 조각 후보 dp[i]
0 (없음)   0
1 a a(조각 아님) ∞
2 ap ap → dp[0] + 1 1
3 app p → dp[2] + 1 = 2, pp → dp[1] + 1 = ∞, app → dp[0] + 1 = 1 1
4 appl l → dp[3] + 1 2
5 apple e → dp[4] + 1 = 3, ple → dp[2] + 1 = 2 2

답은 2다(ap + ple).

7단계 · 복잡도와 흔한 실수

위치 n개 × 길이 5가지 × 자르기(최대 5글자)라 \(O(n)\)에 가깝다. 길이 20,000에서 재 보니 0.1초가 안 걸렸다.

  • 조각마다 문장 전체를 훑어 느려진다. 길이가 5 이하라는 점을 쓴다.
  • 가장 긴 조각부터 욕심껏 붙인다. banana에서 조각 [ban, ba, nana]면 ban을 먼저 붙여 막힌다. ba + nana로 2개다.
  • 만들 수 없을 때 무한대를 그대로 돌려준다.
검증: 문제의 예시 3개를 통과했고, 6단계의 dp 값을 코드로 확인했다. 무작위 입력 3,000개(글자 a·b)에서 “위치를 점, 조각을 간선으로 보고 BFS로 가장 적은 조각 수를 찾는” 풀이와 결과가 같았다. 길이 20,000의 시간도 쟀다 — 30_pg12983_p1.py

  1. 프로그래머스 스쿨, “단어 퍼즐” (https://school.programmers.co.kr/learn/courses/30/lessons/12983), 2026-09-30 조회. ↩