[BOJ]백준 21941번: 문자열 제거(Python)/String, DP

https://www.acmicpc.net/problem/21941

21941번: 문자열 제거

아주 고생고생고생한 DP문제

 

첫 번째 접근: 원래 문자열에서 해당하는 문자열을 삭제하고 중간 문자열들에 대한 최대 점수를 DP로 저장하는 방식(🔥시간초과🔥)

import sys

sys.setrecursionlimit(10**6)
input=sys.stdin.readline

def func(origin):
  global d,cache

  if len(origin)==0:
    return 0
  if cache.get(origin)!=None:
    return cache[origin]

  removed=origin
  if cache.get(origin)==None:
    cache[origin]=0

  for i in range(len(origin)):
    cache[origin]=max(cache[origin],func(origin[:i]+origin[i+1:])+1)

  for key, value in d.items():
    index=removed.find(key)
    if(index==-1): continue

    cache[origin]=max(cache[origin],func(removed[:index]+removed[index+len(key):])+value)

  return cache[origin]

s=input()[:-1]
m=int(input())
d=dict()
cache=dict()

for _ in range(m):
  t=list(map(str,input().split()))
  d[t[0]]=int(t[1])

print(func(s))

 

두 번째 접근: [시작 인덱스, 끝 인덱스]로 이루어진 2차원 DP 배열 (🔥시간초과🔥)

import sys

input=sys.stdin.readline

def dp(s, f):
  global origin, r, cache

  if s>=f: return 0
  if cache[s][f]!=-1: return cache[s][f]
  sub=origin[s:f]

  cache[s][f]=0
  for i in range(s, f):
    cache[s][f]=max(cache[s][f], dp(s, i) + dp(i + 1, f) + 1)

  for recode in r:
    key=recode[0]
    value=recode[1]

    index=sub.find(key)
    if index==-1: continue
    index+=s
    cache[s][f]=max(cache[s][f], dp(s, index) + dp(index+len(key), f) + value)

  return cache[s][f]



origin=input()[:-1]
m=int(input())
cache=[[-1 for _ in range(len(origin)+1)] for _ in range(len(origin)+1)]
r=[]

for _ in range(m):
  r.append(list(map(str,input().split())))
  r[-1][1]=int(r[-1][1])

print(dp(0,len(origin)))

 

세 번째 접근: [시작 인덱스]로 이루어진 1차원 DP 배열 (SOLVED)

DP[i] : origin 문자열의 (i ~ 끝)에 해당하는 부분 문자열이 가질 수 있는 최대 점수

DP 함수의 계산을 위한 재귀 함수에서 index를 인자로 받고,

1️⃣ 해당 인덱스의 문자 1개를 삭제하거나

2️⃣ 해당 문자로부터 후보 문자열의 길이만큼 삭제한다

이 두 가지 케이스에 대해 재귀 함수를 호출하면 끝

import sys

input=sys.stdin.readline

def func(index):
  global origin

  if index>=len(origin): return 0
  if cache[index]!=-1: return cache[index]

  cache[index]=func(index+1)+1

  for recode in r:
    key=recode[0]
    value=recode[1]

    if origin[index:index+len(key)]==key:
      cache[index]=max(cache[index], func(index+len(key))+value)

  return cache[index]

origin=input()[:-1]
m=int(input())
cache=[-1 for _ in range(len(origin)+1)]
r=[]

for _ in range(m):
  r.append(list(map(str,input().split())))
  r[-1][1]=int(r[-1][1])

print(func(0))

처음에는 2차원 DP에 대해서만 생각하다가 1차원 DP로 구현할 시 특정 index 기준에서 1개 문자 삭제/후보 문자 여러개 삭제로 case를 나눌 수 있다는 것을 깨달아서 해결할 수 있었다ㅠ

고난의 흔적