[C] 백준 1958문제 / 3개의 문자열 LCS의 길이 구하기

문제

문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.

이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.

입력

첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다)

출력

첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한다.

제 소스

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define INPUT_COUNT 3
 
void inputString(char **str);
int find3CS(char **str, int seq1, int seq2, int seq3);
void sortString(char **str);
 
int main()
{
    int i, lcs = 0;
    char *str[INPUT_COUNT];
    inputString(str);
    for (i = 0; i < strlen(str[0]); i++) {
        int ccs;
        ccs = find3CS(str, i, 0, 0);
        if (lcs < ccs)    lcs = ccs;
    }
    printf("%d", lcs);
    for (i = 0; i < INPUT_COUNT; i++)    free(str[i]);
}
 
//문자열을 입력받아 동적할당해줌.
void inputString(char **str)
{
    int i;
    char buffer[BUFSIZ];
    for (i = 0; i < INPUT_COUNT; i++) {
        scanf("%s", buffer);
        str[i] = (char*)malloc(strlen(buffer)+1);
        memcpy(str[i], buffer, strlen(buffer) + 1);
    }
}
 
//CS(commom sequence) 찾기 함수
int find3CS(char **str, int seq1, int seq2, int seq3)
{
    int i, j, k;
    char cmpchar;
    sortString(str);
    for (i = seq1; i < strlen(str[0]); i++) {
        cmpchar = str[0][i];
        for (j = seq2; j < strlen(str[1]); j++) {
            if (cmpchar == str[1][j]) {
                for(k = seq3; k < strlen(str[2]); k++)
                    return find3CS(str, i + 1, j + 1, k + 1) + 1;
            }
        }
    }
    return 0;
}
 
//문자열의 길이기준으로 오름차순 정렬
void sortString(char **str)
{
    int i, j, len;
    char *tmp;
    for (i = 0; i < INPUT_COUNT; i++) {
        for (j = 1; j < INPUT_COUNT; j++) {
            if (strlen(str[i]) > strlen(str[j])) {
                tmp = str[i];
                str[i] = str[j];
                str[j] = tmp;
            }
        }
    }
}
Colored by Color Scripter
 cs

제가 직접 실행시켜봤을 때는 문제가 없었는데, 자꾸 제출만 하면 틀렸다고 합니다. 혹시 소스에 문제점이 보이시나요?

(혹시몰라 띄어쓰기도 입력받으려고 scanf대신 gets를 써봤으나 안되네요)