[ 백준 / BOJ 1958 ] LCS 3

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

1958번: LCS 3

문제

---

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

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

 

입력

---

첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.

 

출력

---

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

 

풀이

---

처음에는 문자열 일치하는 최대 substring 의 길이를 구하는 것으로 착각해서 틀렷다.....

substring 이 아니라, subsequence 로 연속되지 않아도 된다‼️

 

그래서 Dynamic Programming 으로 풀었다. 

DP[i][j][k] 는 1번째 문자열의 charAt(i) , 2번째 문자열의 charAt(j), 3번째 문자열의 charAt(k) 까지 일치한 문자의 갯수이다.

 

charAt(i) == charAt(j) == charAt(k) 이면, 

DP[i][j][k] = DP[i-1][j-1][k-1] + 1 이고

 

하나라도 같지 않으면,

DP[i][j][k] = max( DP[i-1][j][k], DP[i][j-1][k], DP[i][j][k-1] ) 이다.

 

코드

---

• 틀린 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] str = new String[3];
        for(int i = 0 ; i < 3; i++){
            str[i] = br.readLine();
        }

        Arrays.sort(str, new Comparator<String>(){
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });

        int minLen = str[0].length();
        int answer = 0;
        boolean flag = false;
        for(int i = minLen ; i >= 0 ; i--){
            for(int j = 0; j < minLen; j++){
                String s;
                if(i + j > str[0].length())
                    s = str[0].substring(j, str[0].length());
                else
                    s = str[0].substring(j, j+i);
                if(str[1].contains(s) && str[2].contains(s)){
                    answer = i;
                    flag = true;
                    break;
                }
            }
            if(flag)
                break;
        }
        System.out.println(answer);
    }
}

• 맞은 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Main_BOJ_1958_LCS3 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] str = new String[3];
        int[] len = new int[3];
        for(int i = 0 ; i < 3; i++){
            str[i] = br.readLine();
            len[i] = str[i].length();
        }

        int[][][] DP = new int[len[0]+1][len[1]+1][len[2]+1];

        for(int i = 1 ; i <= len[0]; i++){
            for(int j = 1 ; j <= len[1] ; j++){
                for(int k = 1 ; k <= len[2] ; k++){
                    if(str[0].charAt(i-1) == str[1].charAt(j-1) && str[1].charAt(j-1) == str[2].charAt(k-1)){
                        DP[i][j][k] = DP[i-1][j-1][k-1] + 1;
                    }
                    else{
                        DP[i][j][k] = Math.max(DP[i-1][j][k], Math.max(DP[i][j-1][k], DP[i][j][k-1]));
                    }
                }
            }
        }

        System.out.println(DP[len[0]][len[1]][len[2]]);
    }
}