김민지

2.문제이름

3. 수행시간[초(s)]

3600

4. git 주소 URL

https://github.com/Min-ji99/BES2-AlgorithmStudy/blob/main/PG/DP/PG_12983.py

좋아요 누르기

좋아요 수

: 0

5 more properties

| 코드 작성하기

def solution(strs, t):
    answer = 0
    n=len(t)
    dp=[float('inf')]*(n+1)
    dp[0]=0
    for i in range(1, n+1):
        for k in range(1, 6):
            if i<k : start = 0
            else : start=i-k

            if t[start:i] in strs :
                dp[i]=min(dp[i], dp[i-k]+1)
    if dp[-1]==float('inf') :
        return -1
    else : return dp[-1]
Python
복사

| 코드 설명하기

dp[i]는 문자열 t의 index i 까지 만들 수 있는 단어조각 중 최소개수를 의미한다.

t의 길이+1만큼의 dp 리스트를 만들고 가장 큰 수로 초기화 시켜준다.

dp[0]을 0으로 초기화시킨다.

1부터 n까지 dp 리스트를 채워나간다.

strs의 단어조각의 길이가 1이상 5이하이므로 1부터 5까지 반복한다.

i-k부터 t의 현재 인덱스까지와 동일한 단어조각이 있는지 확인을 한다.

있으면 현재 dp 값과 dp[i-k]+1 한 값중 최소값으로 갱신한다.

dp[-1](t를 만들 수 있는 최소 개수)가 처음 초기값이면 -1을 반환하고 아니면 만들수 있는 최소 단어 개수를 반환한다.

예시

strs : ["app","ap","p","l","e","ple","pp"]

t : "apple"

i가 1일 때 “a”를 만들 수 있는 경우가 없으므로 dp[1]=’inf’이다.

i가 2일 때 “ap”를 만들 수 있는 경우

“p”로 만드는 경우 dp[2]와 dp[1]+1(’inf’) 중에 최소 이므로 dp[2]는 갱신되지 않는다.

“ap”로 만드는 경우 dp[2]와 dp[0]+1 중에 최소 이므로 dp[2]=1

i가 3일 때 “app”을 만들 수 있는 경우

“p”로 만드는 경우는 dp[3]과 dp[2]+1 중에 최소이므로 dp[3]=2

“pp”로 만드는 경우는 dp[3]과 dp[1]+1=’inf’ 중에 최소이므로 갱신되지 않는다.

“app”로 만드는 경우는 dp[3]과 dp[0]+1 중에 최소이므로 dp[3]=1

i가 4일 때 “appl”를 만들 수 있는 경우

“l”로 만드는 경우 dp[4]와 dp[3]+1 중에 최소이므로 dp[4]=2

i가 5일 때 “apple”를 만들 수 있는 경우

“e”로 만드는 경우 dp[5]와 dp[4]+1 중에 최소이므로 dp[5]=3

“ple”로 만드는 경우 dp[5]와 dp[2]+1 중에 최소이므로 dp[5]=2