베시는 유명 대전 격투 게임 Mootal Cowmbat의 오랜 플레이어다. 그런데, 게임 개발자들이 밸런스 패치를 해서 베시는 자신이 쓰던 콤보를 수정해야만 한다!
이 게임은 'a'부터 순서대로 M개의 알파벳 소문자 버튼을 사용하고 (1≤M≤26), 베시가 이 게임에서 가장 좋아하는 콤보는 누르는 버튼 순서대로 길이가 N인 문자열 S로 나타낼 수 있다 (1≤N≤100 000).
하지만 이번 패치 내역에서 모든 콤보는 반드시 "연타"로만 구성되도록 바뀌었다. 여기서 연타란 같은 버튼을 K번 이상 연속으로 누르는 것을 의미한다 (1≤K≤N). 베시는 패치 내역에 맞게, 자신의 콤보를 연타만으로 이루어진 길이 N의 새로운 콤보로 바꾸려고 한다.
베시가 콤보를 바꿀 때, 콤보의 어느 지점인지는 상관 없이 i 버튼 대신 j 버튼으로 바꿔 누르는 것을 연마하는 데 aij 일만큼 걸린다. (즉, S에서 특정 글자 i를 j로 바꾸는 데 aij만큼의 비용이 든다.)
그런데 i 버튼을 j 버튼으로 바꿔 누르는 것보다, i 버튼을 일단 k 버튼으로 바꿔 누르고 그 다음에 k 버튼을 j 버튼으로 바꿔 누르는 데 걸리는 기간이 더 짧을 수도 있다. (다르게 말하면, 버튼 i를 버튼 j로 바꿔서 누를 때 중간에 다른 버튼을 거쳐서 가는 것도 가능하다.)
베시가 패치 내역에 맞게 콤보를 고쳐서 연마하는 최소 기간을 계산해 보자!
<입력>
첫째 줄에 N, M, 그리고 K가 주어진다.
둘째 줄에 S가 주어진다.
그 다음 M개 줄에 걸쳐 MxM의 aij 행렬 데이터가 주어지는데, aij는 0부터 1000 사이의 정수이고 모든 i에 대해 aii=0이다.
<출력>
베시가 콤보를 패치 내역에 맞게 수정하는 최소 일수를 출력한다.
<예제 입력 1>
5 5 2
abcde
0 1 4 4 4
2 0 4 4 4
6 5 0 3 2
5 5 5 0 4
3 7 0 5 0
<예제 출력 1>
5
<힌트>
M=5개의 알파벳 소문자 버튼을 사용하므로 알파벳 'a', 'b', 'c', 'd', 'e' 버튼을 사용한다.
이 예제의 최적 해는 콤보의 a 버튼을 b 버튼으로 바꿔서 bbcde로 바꾸고, d 버튼은 e 버튼으로 바꿔서 bbcee로 바꿨다가, 두 개의 e 버튼을 모두 c로 바꿔서 bbccc로 바꾸는 것이다. 이렇게 연마하는 데에 1+4+0+0=5일이 걸린다.
mosqcoil 1년 전
베시는 유명 대전 격투 게임 Mootal Cowmbat의 오랜 플레이어다. 그런데, 게임 개발자들이 밸런스 패치를 해서 베시는 자신이 쓰던 콤보를 수정해야만 한다!
이 게임은 'a'부터 순서대로 M개의 알파벳 소문자 버튼을 사용하고 (1≤M≤26), 베시가 이 게임에서 가장 좋아하는 콤보는 누르는 버튼 순서대로 길이가 N인 문자열 S로 나타낼 수 있다 (1≤N≤100 000).
하지만 이번 패치 내역에서 모든 콤보는 반드시 "연타"로만 구성되도록 바뀌었다. 여기서 연타란 같은 버튼을 K번 이상 연속으로 누르는 것을 의미한다 (1≤K≤N). 베시는 패치 내역에 맞게, 자신의 콤보를 연타만으로 이루어진 길이 N의 새로운 콤보로 바꾸려고 한다.
베시가 콤보를 바꿀 때, 콤보의 어느 지점인지는 상관 없이 i 버튼 대신 j 버튼으로 바꿔 누르는 것을 연마하는 데 aij 일만큼 걸린다. (즉, S에서 특정 글자 i를 j로 바꾸는 데 aij만큼의 비용이 든다.)
그런데 i 버튼을 j 버튼으로 바꿔 누르는 것보다, i 버튼을 일단 k 버튼으로 바꿔 누르고 그 다음에 k 버튼을 j 버튼으로 바꿔 누르는 데 걸리는 기간이 더 짧을 수도 있다. (다르게 말하면, 버튼 i를 버튼 j로 바꿔서 누를 때 중간에 다른 버튼을 거쳐서 가는 것도 가능하다.)
베시가 패치 내역에 맞게 콤보를 고쳐서 연마하는 최소 기간을 계산해 보자!
<입력>
첫째 줄에 N, M, 그리고 K가 주어진다.
둘째 줄에 S가 주어진다.
그 다음 M개 줄에 걸쳐 MxM의 aij 행렬 데이터가 주어지는데, aij는 0부터 1000 사이의 정수이고 모든 i에 대해 aii=0이다.
<출력>
베시가 콤보를 패치 내역에 맞게 수정하는 최소 일수를 출력한다.
<예제 입력 1>
5 5 2
abcde
0 1 4 4 4
2 0 4 4 4
6 5 0 3 2
5 5 5 0 4
3 7 0 5 0
<예제 출력 1>
5
<힌트>
M=5개의 알파벳 소문자 버튼을 사용하므로 알파벳 'a', 'b', 'c', 'd', 'e' 버튼을 사용한다.
이 예제의 최적 해는 콤보의 a 버튼을 b 버튼으로 바꿔서 bbcde로 바꾸고, d 버튼은 e 버튼으로 바꿔서 bbcee로 바꿨다가, 두 개의 e 버튼을 모두 c로 바꿔서 bbccc로 바꾸는 것이다. 이렇게 연마하는 데에 1+4+0+0=5일이 걸린다.