BOJ 5905 악당 로봇 (Video Game)

 

문제 링크 : https://www.acmicpc.net/problem/5905

5905번: 악당 로봇

 

'콤보' 라는 이름으로 패턴들이 주어진다.

검색 대상 스트링이 주어지고 거기에 콤보가 몇 번이나 발생한 것인지를 묻는다면, 평범한 스트링 문제일 것이다.

하지만 길이 K 이하의 문자열로 최대의 콤보가 발생하게 만들어야 하는 상황이니 dp 외에 뚜렷한 방법이 생각나지 않는다. 

 

1. 필요한 정보들 

(1) added[i][j] 

added[i][j] :콤보 i 에 1 문자 이상을 더해서 콤보 j 로 끝나는 문자열을 만드는 최소의 길이.

예를 들어 combo[i]='xbcbc' 이고 combo[j]='bcbcy' 일 때,

combo[i]+'y' 혹은 combo[i]+'bcy' 는 모두 combo[j] 로 끝나는 문자열이 된다.

여기서는 최소의 것이라 했으니 added[i][j]=1 이 된다. 

여기서 우리가 배제한 'bcy' 를 더하는 경우는 added[j][j] 에서 반영될 것이므로 걱정할 것 없다.

 

(2) contains[i][rIdx] 

contains[i][rIdx] : combo[i] 에서 뒤에서부터 rIdx 위치 까지에서 끝나는 다른 콤보의 누적 개수.

써놓고 보니까 국어를 잘 못한다는 사실을 새삼 깨닫게 된다. 별 수 없다 예를 보자.

combo[i]='abc' 라 하자. rIdx 는 뒤쪽에서 시작한 인덱스이므로 rIdx=1 은 마지막 문자까지 일치한 콤보 개수의 합산이다.

예를 들어 combo[j]='bc'  이면 contains[i][1] 에 1 기여하게 된고 combo[j]='ab' 이면 contains[i][2] 에 1 기여한다. 

 

참고로 이 단계에서 Aho-Corasick 알고리즘을 적용할 수 있지만 backward 누적 계산까지 처리하는 방법은 찾지 못했다.

콤보의 개수가 최대 20 개이고 각각의 길이가 최대 15 이므로 모두 직접 조사해도 20*20*15 이어서 그냥 무식하게 계산했다.

 

2. Trainsition 

dp 를 다음과 같이 정의하자.

dp[k][i] : 현재까지 입력된 문자열의 길이가 k 이고 i 번 콤보로 끝날 때 누적 콤보 개수의 최대값.

문자열을 만들어갈 때 콤보로 끝나지 않으면 세어질 이유가 없음은 이해가 될 것이다.

현재의 길이 k 보다 길면서 j 콤보로 끝나는 문자열은 다음과 같이 될 것이다.

target = k+added[i][j];

dp[target][j]=max( dp[target][j], dp[k][i]+contains[j][added[i][j]] )

 

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int N, K;

struct Combo{
    char word[16];
    int len;
};
Combo combo[21];

bool suffix_prefix_match(int i,int j, int len) {
    int start = combo[i].len-(combo[j].len-len);
    return strncmp(combo[i].word+start, 
    			   combo[j].word, 
                   combo[j].len-len) == 0;
}

int added[21][21];
void calculate_transition_length(){
    for(int i=0;i<N;i++) for(int j=0;j<N;j++){
            int added_length=max(1,combo[j].len-combo[i].len);
            for(;added_length<=combo[j].len; added_length++)
                if(suffix_prefix_match(i,j,added_length)){
                    added[i][j]=added_length;
                    break;
                }
        }
}

int contains[21][16];
void count_combo(){
    for (int i=0; i< N; i++) {
        contains[i][0] = 0;
        for (int last=combo[i].len, rIdx=0; last>=0; last--, rIdx++) {
            int cnt=0;
            for (int j=0; j<N; j++)
                if (last<combo[j].len) continue;
                else if(strncmp(combo[i].word+last-combo[j].len, 
                                combo[j].word,
                                combo[j].len) == 0)
                    cnt++;

            contains[i][rIdx+1]=contains[i][rIdx]+cnt;
        }
    }
}

int dp[1001][21];
void solve(){
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < N; i++)
        dp[combo[i].len][i] = contains[i][combo[i].len];

    int ans = 0;
    for (int k = 0; k <= K; k++) for (int i = 0; i < N; i++)
            if (dp[k][i] >= 0) {
                ans = max(ans, dp[k][i]);
                for (int j = 0; j < N; j++) {
                    int target = k + added[i][j];
                    if (target <= K)
                        dp[target][j] = max(dp[target][j], 
                                     dp[k][i] + contains[j][added[i][j]]);
                }
            }

    printf("%d\n", ans);
}

int main(){
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++){
        scanf("%s", combo[i].word);
        combo[i].len = strlen(combo[i].word);
    }

    count_combo();
    calculate_transition_length();

    solve();
    return 0;
}

 

아무래도 설명히 심히 구리다.

차후에 그림을 추가해서 조금 더 상세히 기술하도록 하겠다.