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

import sys

def input():
    return sys.stdin.readline().rstrip()

def dfs(idx):
    if idx >= N:
        return 0

    if dp[idx] != -1:
        return dp[idx]
    max_value = 0
    for string_key in score_dict.keys():
        score,len_string = score_dict[string_key]
        if idx + len_string-1<N:
            for check_idx in range(len_string):
                if input_string[check_idx+idx] != string_key[check_idx]:
                    break
            else:
                max_value = max(max_value,score + dfs(idx+len_string))
    max_value = max(max_value,1+dfs(idx+1))
    dp[idx] = max_value
    return dp[idx]
                

input_string = input()
N = len(input_string)
M = int(input())
score_dict = {}
for _ in range(M):
    string,score = input().split()
    score_dict[string] = [int(score),len(string)]



dp = [-1]*(N+1)

print(dfs(0))

 

 

문제를 푼 방식은 다음과 같다.

 

문제에 주어진 문자열들을 문자열을 key로 하고, 점수와 길이를 value로 하는 dictionary에 넣어둔다.

 

그리고 0번인덱스부터 재귀를 돌면서

 

현재 위치에서부터 문자열이 일치하는 경우에 재귀를 하면서 최대값을 구한다.

 

그리고 일치하지 않을때를 위해, dfs(idx+1)+1 현재위치의 문자열만을 제거했을때도 구해주면된다.

 

그리고 dp값을 변환시켜주면 된다.