BOJ 31092(스티커 재배치) 풀이

이미지를 누르면 문제로 이동합니다

 

이 문제는 초기 문자열과 만들어야하는 문자열이 주어질 때, 각 위치의 스티커를 떼고 붙이고, 구매 등의 방법을 사용해   만들어야하는 문자열이 초기 문자열의 부분 문자열이 되도록 하는 최소값을 구하는 문제이다.

 

문제 설명만 봤을 때는 어려워 보일 수도 있지만 문자열의 길이가 500이 안되기 때문에 모든 경우를 탐색하면서 최소값을 계산해주면 된다.

 

부분 문자열을 만들 수 없는 경우 -1을 출력하라고 되어있는데, 이는 구매할 수 있는 스티커 중에 부분 문자열에 필요한 스티커가 없을 때 -1을 출력해주면 된다.

 

부분 문자열을 만들기 위해서 부분 문자열에 해당될 부분 중, 바꿔야 될 부분의 스티커를 모두 떼준다. 그후 뗀 스티커와 다른 범위에 있는 스티커까지 고려해서 어느걸 고르는 것이 최소값이 되는지 판단해주면 된다.

만약 이미 뗀게 있다면 그것을 붙이는게 최소값을 이루게 될것이고, 뗀게 없을 때, 구매하는 방법과 다른 범위에서 떼서 붙이는 두가지 방법이 있는데 이 중 값이 더 작은 쪽을 선택해주면 된다.

구매하는 경우에는 입력에서 같은 스티커가 여러번 나올 수 있기 때문에 같은 스티커 중 가장 구매 비용이 작은 것을 골라주면된다.

이 모든 과정을 N-K+1 번 반복하면서 해주면 되고, 각 경우마다 최소값을 구하기 위해 Priority Queue 를 쓰기 때문에 시간 복잡도는 O(N^2logN) 이 된다.

 

import sys,math
from queue import PriorityQueue
inf=math.inf
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
n,m,k=map(int,input().split())
st=[list(input().strip().split())for i in range(m)]
b=list(map(int,input().split()))
s=input().strip()
r={}
txt=[]
for i in range(m):
    st[i][1]=int(st[i][1])
    st[i][2]=int(st[i][2])
    if st[i][0] in txt:
        r[st[i][0]]=min(r[st[i][0]],st[i][2])
    else:
        r[st[i][0]]=st[i][2]
        txt.append(st[i][0])

def er(s):
    for i in range(k):
        if not s[i] in txt:
            return 0
        else:
            In[s[i]]=1
    return 1

In={txt[i]:0 for i in range(len(txt))}
if er(s)==0:
    print(-1)
    sys.exit()
    

ans=inf
for i in range(n-k+1):

    a_cost=0
    off={txt[g]:PriorityQueue() for g in range(len(txt))}
    for g in range(n):
        if i<=g<=i+k-1:
            if s[g-i]!=st[b[g]-1][0]:
                if In[st[b[g]-1][0]]==1:
                    off[st[b[g]-1][0]].put(0)
                a_cost+=st[b[g]-1][1]
        else:
            if In[st[b[g]-1][0]]==1:
                off[st[b[g]-1][0]].put(st[b[g]-1][1])

    for g in range(i,i+k):
        #st[b[g]-1]
        nt=st[b[g]-1][0]
        if s[g-i]!=nt:
            if off[s[g-i]].qsize()>0:
                v=off[s[g-i]].get()
                if v<r[s[g-i]]:
                    a_cost+=v
                else:
                    a_cost+=r[s[g-i]]
                    off[s[g-i]].put(v)
            else:
                a_cost+=r[s[g-i]]
                    

            
    ans=min(ans,a_cost)


print(ans)