[백준] 1958. LCS3(골드3)

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

풀이

처음에는 첫번째 문자열과 두번째 문자열을 비교한 후, 그 결과를 세번째 문자열과 비교하면 된다고 생각을 했었다.
그렇게 된다면 많은 예외케이스가 나오게된다.
s1 = aaaacde
s2 = aaaacd
s3 = cd
일 경우 완전 오답이 나온다.
s1,s2를 비교했을 경우에 lcs는 aaaa가 된다.
그리고 aaaa와 s3을 비교하게 된다면 결과는 빈 문자열이 되어버린다.
하지만 실제 정답은 cd이다.

차례대로 비교해서 답을 구하는게 아니라 세 문자열을 동시에 비교해야한다.
그래서 3차원 배열로 lcs를 구하니 정답이 나왔다!!

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static String s1,s2,s3;
	static int[][][] dp;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		s1 = br.readLine();
		s2 = br.readLine();
		s3 = br.readLine();
		
		dp = new int[s1.length()+1][s2.length()+1][s3.length()+1];
		lcs();
		
		
		System.out.println(dp[s1.length()][s2.length()][s3.length()]);
		
	}

	private static void lcs() {
		for(int i=1; i<=s1.length(); i++) {
			for(int j=1; j<=s2.length(); j++) {
				for(int k=1; k<=s3.length(); k++) {
					if(s1.charAt(i-1) == s2.charAt(j-1) && s2.charAt(j-1) == s3.charAt(k-1)) {//같은 경우
						dp[i][j][k] = dp[i-1][j-1][k-1]+1;
					}else {//같지 않을 경우
						int temp = Math.max(dp[i-1][j][k], dp[i][j-1][k]);
						dp[i][j][k] = Math.max(temp, dp[i][j][k-1]);

					}
				}
			}
		}
	}

}