[Python] BOJ 백준 21941 문자열제거

문제

---

지우고 싶은 문자열 S와 지울 수 있는 문자열 A{1}, A{2}, ..., A{M}이 주어진다. 문자열 A{i}들은 각자 X{i}라는 점수를 가진다. 이 때, 문자열 S를 삭제 연산을 이용하여 모두 제거하려고 한다.

삭제 연산은 두 가지 방법이 존재하며, 원하는 만큼 여러 번에 걸쳐서 수행할 수 있다.

1. 문자열 S의 부분 문자열 중에 문자열 A{i} 가 존재한다면 해당하는 부분을 지우고 X{i} 만큼의 점수를 얻는다(여러 부분 존재해도 한 번만 지운다).
2. 문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다.

예를 들어, 문자열 S가 "abcxyzxabc"이 있고 "abc" 문자열을 지울 경우 10점, "xyz" 문자열을 지울 경우 5점을 얻는다고 하자. 문자열을 모두 제거하여 최대 점수를 얻을 수 있는 과정은 아래와 같다.

• 문자열 S에서 문자열 "xyz" 하나를 지운다. 현재 총 얻은 점수는 5점이고 문자열 S$S$는 "abc___xabc"가 된다. 이때, '_'는 문자가 지워진 자리를 의미한다.
• 문자열 S에서 문자열 "abc" 하나를 지운다. 현재 총 얻은 점수는 15점이고 문자열 S는 "______xabc"가 된다.
• 문자열 S에서 문자열 "abc" 하나를 지운다. 현재 총 얻은 점수는 25점이고 문자열 S는 "______x___"가 된다.
• 남은 문자들을 하나씩 지운다. 현재 총 얻은 점수는 26점이고 문자열 S는 빈 문자열이 된다.

문자열을 모두 제거하여 얻을 수 있는 최대 점수는 26점이다. 이보다 더 얻을 수 있는 점수는 없다.

삭제 연산을 이용하여 문자열 S을 지울려고 할 때 얻을 수 있는 최대 점수는 몇 점인지 계산하자.

---

풀이

---

여러 가지 방법을 시도해봤다. re를 이용해서 문자열을 줄이는 방법과, 단순 슬라이싱으로 바꾸는 방법, replace 등등

많은 삽질이 있었으나 전부 실패했다. 투포인터를 이용해서 인덱스로 접근을 해보려다가,

같은 스터디원이 전에 무슨 문제인지 모르겠으면 다이나믹 프로그래밍 문제라는 말을 했던 것이 생각나서 dp로 구현해봤다.

문자열을 하나 지우면 1점을 얻을 수 있기 때문에 이를 식으로 만들어서 재귀함수와 dp로 구현했다.

주의할 점은 이미 갱신 되었는지 체크해주는 것과 문자열의 길이를 인덱스가 초과하면 바로 return 0을 해줘야 한다.

import sys
from math import inf


si = sys.stdin.readline
sys.setrecursionlimit(10**8)

def MSIS():
    return map(str, si().split())


s = si().rstrip()
m = int(si())

table = []
score = [-inf for _ in range(len(s))]
for _ in range(m):
    temp = list(MSIS())
    table.append([temp[0], int(temp[1])])


def solution(start):
    global score
    # 문자열 s의 길이를 초과하면 얻는 점수 0
    if start >= len(s):
        return 0
    if score[start] != -inf:
        return score[start]
    # start번째의 점수는 start + 1번째의 함수가 가질 수 있는 점수 + start번째를 삭제하는 점수
    score[start] = solution(start + 1) + 1
    # key value를 받아온다.
    for k, v in table:
        # print(f"start = {start}, k = {k}, v = {v}")
        # s의 start번째에서 k가 발견되면
        if s[start:start + len(k)] == k:
            # score의 start번째에서 얻을수 있는 점수를 구해낸다.
            # 원래 점수와 k번째 문자열로 점수를 얻었을 때를 비교
            score[start] = max(score[start], solution(start + len(k)) + v)
            # print(f"start = {start}, score is now {score}")

    return score[start]


print(solution(0))