[백준] 1958번 LCS3

1958번: LCS 3

예제 보고 이해하기

기존 LCS1,2는 문자열 두개를 대상으로 구하는 것이었다.

str1[i]에 대하여....

• str2[j]는 같을수도, 다를 수도
• str3[k]는 같을 수도, 다를수도,

기존의 LCS를 구하던 방식은

cache[idx1][idx2] :

• str1의 0~ idx 1 까지와
• str2의 0~ idx2까지에
• 대한 LCS의 길이를 구하는 것이었다.

따라서 str1과 str2에 대한 LCS를 구하고 → lcs1

str1과 str3에 대한 LCS를 구하는 → lsc2 과정을 펼친다면??

그리고는 lcs1과 lcs2의 LCS를 구한다면?

근데 여기서 걱정되는 것은

• LCS를 구할 때면, 같은 길이를 갖는 여러개의 LCS가 나올 수 있다는 것이다.

그렇다면, lcs1을 구하는 과정에서 lcs2도 함께 구할 수는 없을까?

풀지못했다 : 다른 사람 풀이

(1시간 고민 ㅠ )

아예 동시에 LCS를 구하는 것이 가능하다.

이전에, 두 개의 문자열로만 구하던 것과 같이 할 수 있다.

IF) str1,str2를 비교한 후, str1,str3를 따로 비교하는 것이 아니라, 3중 포문을 돌려, i==j==k인 지점을 찾아야 한다.

ELSE ) str1[i],str2[j],str3[k]중에서 하나라도 다른 경우 → cache[i-1][j][k], cache[i][j-1][k], cache[i][j][k-1]중 max 값을 찾는다.

for(int i=0;i<str1.length();i++){
	for(int j=0;j<str2.length();j++){
		for(int k=0;k<str3.length();k++){
			// cache[i-1][j][k]
			// cache[i][j-1][k]
			// cache[i][j][k-1] 

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main{
    public static int[][][] cache;
    public static String[] inputs = new String[3];
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void setting() throws IOException {
        for(int i=0;i<3;i++){
            inputs[i] = br.readLine();
        }

    }
    public static void solve(){
        int[] lens = new int[3];
        for(int i=0;i<3;i++){
            lens[i] = inputs[i].length();
        }
        cache = new int[lens[0]+1]
                [lens[1]+1]
                [lens[2]+1];
        int max = 0;
        for(int i=1;i<=lens[0];i++){
            for(int j=1;j<=lens[1];j++){
                for(int k=1;k<=lens[2];k++){
                    max = 0;
                    if((inputs[0].charAt(i-1)==inputs[1].charAt(j-1))&&(inputs[1].charAt(j-1)==inputs[2].charAt(k-1))){
                        cache[i][j][k]=cache[i-1][j-1][k-1]+1;
                    }else{
                        max = Math.max(cache[i-1][j][k],max);
                        max = Math.max(cache[i][j-1][k],max);
                        max = Math.max(cache[i][j][k-1],max);
                        cache[i][j][k] = max;
                    }
                }
            }
        }
    }
    public static void main(String[] args)throws IOException {
        setting();
        solve();
        System.out.println(cache[inputs[0].length()][inputs[1].length()][inputs[2].length()]);

    }
}