[BOJ] 1958번: LCS 3

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

1958번: LCS 3

알고리즘 분류

* 다이나믹 프로그래밍

* 문자열

 

9251번 문제 LCS

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

 

9252번 문제 LCS 2

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

 

위의 두 문제에 이어서 LCS 3 문제이다.

 

기존 문제는 문자열 2개를 기준으로 최장 공통 부분 수열을 구했다면

이번 문제는 문자열 3개를 기준으로 문제를 풀어나가야 한다.

 

첫번째 시도

나의 생각 => 문자열 2개를 기준으로 만들어진 LCS를 남은 문자열과 함께 다시 LCS를 구하면 되지 않을까 하고 접근 했다.

결과 : 실패

원인 : 아래와 같은 반례가 있었다. 해가 유일하지 않다는 점도 있어서 문제 접근을 잘못 한 것 같다.

A: dababcf
B: ababdef
C: df

LCS(A,B): ababf
LCS(LCS(A,B),C):  f
LCS(A,B,C): df

<실패 소스>

/* 
 * 
 * 다이나믹 프로그래밍, 문자열
 * 1958번 : LCS 3
 */
import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) throws Exception {		
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		char[] A = br.readLine().toCharArray();
		char[] B = br.readLine().toCharArray();
		char[] C = br.readLine().toCharArray();
		
		
		int[][] dp = new int[A.length+1][B.length+1];
		
		char[] s = LCS(A,B).toCharArray();
		
		String answer;
		if(s.length> C.length) {
			answer = LCS(s,C);
		}
		else {
			answer = LCS(C,s);
		}
		
		System.out.println(answer.length());
	}
	
	public static String LCS(char[] A , char[] B) {
		
		StringBuilder sb = new StringBuilder();
		
		int[][] dp = new int[A.length+1][B.length+1];
		
		for(int row = 1; row<A.length+1;row++)
		{
			for(int col=1;col<B.length+1;col++)
			{
				if(A[row-1] == B[col-1]) {
					dp[row][col] = dp[row-1][col-1]+1;
				}
				else {
					dp[row][col] = Math.max(dp[row-1][col],dp[row][col-1]);
				}
			}
		}		
		
		int row = A.length;
		int col = B.length;
		while(row >0 && col >0)
		{
			if(dp[row][col] == dp[row-1][col]) {
				row--;
			}
			else if(dp[row][col] == dp[row][col-1]) {
				col--;
			}
			else {
				sb.append(A[row-1]);
				row--;
				col--;
			}
		}
		
		sb.reverse();
		return sb.toString();
	}
}

그 이후 코드 수정하여 통과

<통과 소스>

/* 
 * 다이나믹 프로그래밍, 문자열
 * 1958번 : LCS 3
 */
import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) throws Exception {		
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		char[] A = br.readLine().toCharArray();
		char[] B = br.readLine().toCharArray();
		char[] C = br.readLine().toCharArray();
		
		int[][][] dp = new int[A.length+1][B.length+1][C.length+1];		
		
		for(int row = 1; row<A.length+1; row++)
		{
			for(int col = 1; col<B.length+1; col++)
			{
				for(int depth = 1; depth<C.length+1; depth++)
				{
					if(A[row-1] == B[col-1] && B[col-1] == C[depth-1]) {
						dp[row][col][depth] = dp[row-1][col-1][depth-1]+1;
					}
					else {
						dp[row][col][depth] = Math.max(dp[row-1][col][depth],Math.max(dp[row][col-1][depth],dp[row][col][depth-1]));
					}
				}
			}
		}		
		System.out.println(dp[A.length][B.length][C.length]);
	}
}