[Gold IV] LCS 3 - 1958
성능 요약
메모리: 17568 KB, 시간: 132 ms
분류
다이나믹 프로그래밍, 문자열
제출 일자
2024년 6월 21일 15:47:06
문제 설명
문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.
이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.
입력
첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.
출력
첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한다.
접근 방법
1. 3차원 배열을 통해 한번에 계산해줘야한다.
2. LCS(a,b,c) != LCS( LCS(a,b) , c) 이라서 한번에 해줘야한다.
이해를 돕기 위한 반례:
Input
abbbccc
bbbaddd
cccddda
LCS( "abbbccc", "bbbaddd") = "bbb"
LCS( "bbbaddd", "cccddda") = "ddd"
LCS("abbbccc", "bbbaddd", "cccddda") = "a"
풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* 문제: BOJ_1958_LCS3
* 메모리: 17676KB
* 시간: 140ms
* 접근 방법
* 1. 3차원 배열을 통해 한번에 계산해줘야한다.
* 2. LCS(a,b,c) != LCS(LCS(a,b),c) 이라서 한번에 해줘야한다.
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String a = br.readLine();
String b = br.readLine();
String c = br.readLine();
System.out.println(getLCS(a, b, c));
}
private static int getLCS(String a, String b, String c) {
int aLen = a.length(), bLen = b.length(), cLen = c.length();
int[][][] dp = new int[aLen + 1][bLen + 1][cLen + 1];
for (int i = 1; i <= aLen; i++) {
char aChar = a.charAt(i - 1);
for (int j = 1; j <= bLen; j++) {
char bChar = b.charAt(j - 1);
for (int k = 1; k <= cLen; k++) {
char cChar = c.charAt(k - 1);
if (aChar == bChar && bChar == cChar) {
dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
} else {
dp[i][j][k] = Math.max(Math.max(dp[i - 1][j][k], dp[i][j - 1][k]), dp[i][j][k - 1]);
}
}
}
}
return dp[aLen][bLen][cLen];
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 18513번 : 샘터 Gold4(골드4) - JAVA[자바] (0) | 2024.06.19 |
---|---|
[백준] 14391번 : 종이 조각 Gold3(골드3) - JAVA[자바] (0) | 2024.06.19 |
[백준] 14284번 : 간선 이어가기2 Gold5(골드5) - JAVA[자바] (0) | 2024.06.18 |
[백준] 2374번 : 같은 수로 만들기 Gold4(골드4) - JAVA[자바] (0) | 2024.06.18 |
[백준] 10282번 : 해킹 Gold4(골드4) - JAVA[자바] (1) | 2024.06.18 |