파이썬으로 문자열 생성을 위한 최소 비용 계산하기

길이가 n인 문자열 str을 만들어야 한다고 가정해 봅시다. 문자열을 구성하기 위해 다음 두 가지 연산을 사용할 수 있습니다.

• 문자 하나를 문자열 끝에 추가하는 연산 — 비용 a
• 부분 문자열(sub_str)을 문자열 끝에 추가하는 연산 — 비용 r

목표는 문자열 str을 완성하는 데 드는 최소 비용을 구하는 것입니다.

예시

입력: a = 5, r = 4, str = 'tpoint'

출력: 29

비용 상세 내역

str = 't'   ; 새 문자 추가 → 비용 5
str = 'tp'  ; 새 문자 추가 → 비용 5
str = 'tpo' ; 새 문자 추가 → 비용 5
str = 'tpoi'; 새 문자 추가 → 비용 5
str = 'tpoin'; 새 문자 추가 → 비용 5
str = 'tpoint'; 부분 문자열 't' 추가 → 비용 4

총 비용 = 5 + 5 + 5 + 5 + 5 + 4 = 29

해결 알고리즘

1. size ← 문자열 길이
2. largest ← 빈 리스트 (각 위치에서 재사용 가능한 최대 부분 문자열 길이 저장)
3. low ← 0
4. upp를 1부터 size까지 순회하며:
   
   • str[low:upp]가 str[:low]에 없을 동안 low 증가
   • upp - low를 largest에 추가
5. c ← [a] (누적 최소 비용 배열, 첫 글자는 무조건 문자 추가)
6. i를 1부터 size-1까지 순회하며:
   
   • largest[i] == 0이면: c.append(c[-1] + a) (재사용 불가 → 문자 추가)
   • 그렇지 않으면: c.append(min(c[-1] + a, c[i - largest[i]] + r)) (문자 추가 vs 부분 문자열 추가 중 최소값)
7. c[-1] 반환 (최종 최소 비용)

파이썬 구현

def solve(a, r, s):
    size = len(s)
    largest = []
    low = 0
    
    for upp in range(1, size + 1):
        while s[low:upp] not in s[:low]:
            low += 1
        largest.append(upp - low)

    c = [a]
    for i in range(1, size):
        if largest[i] == 0:
            c.append(c[-1] + a)
        else:
            c.append(min(c[-1] + a, c[i - largest[i]] + r))

    return c[-1]

print(solve(5, 4, 'tpoint'))  # 출력: 29

입력

5, 4, 'tpoint'

출력

29