[백준] G3 1958번 LCS 3 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

1958번: LCS 3

[문제] 

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

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

[입력]

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

[출력]

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

 

---

[풀이]

1. 문자열들을 입력받아준다.

2. dp 배열을 3차원으로 만들어 각 문자열 길이 + 1만큼 크기를 지정해준다.

3. 반복을 돌면서 LCS알고리즘을 사용해서 문제를 풀어준다.

4. 결과를 출력한다.

[접근]

1. 이전에 풀었던 LCS 문제는 2차원 배열을 사용했다면 이번에는 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));
		
		String str1 = br.readLine();
		String str2 = br.readLine();
		String str3 = br.readLine();
		
		int[][][] dp = new int[str1.length() + 1][str2.length() + 1][str3.length() + 1];
		
		for (int i = 1; i <= str1.length(); i++) {
			for (int j = 1; j <= str2.length(); j++) {
				for (int k = 1; k <= str3.length(); k++) {
					if (str1.charAt(i - 1) == str2.charAt(j - 1) && str2.charAt(j - 1) == str3.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[str1.length()][str2.length()][str3.length()]);
	}
}