반응형
출처: https://www.acmicpc.net/problem/1958
Input
abcdefghijklmn
bdefg
efg
Output
3
두 문자열을 입력받아 LCS를 출력하는 문제
LCS (Longest Common Subsequence) 알고리즘
3개의 문자열에서 LCS를 출력하는 문제로 3차원 배열을 활용하여 해결
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] A = sc.next().toCharArray();
char[] B = sc.next().toCharArray();
char[] C = sc.next().toCharArray();
int[][][] LCS = new int[A.length+1][B.length+1][C.length+1];
for(int i=1; i<=A.length; i++) {
for(int j=1; j<=B.length; j++) {
for(int k=1; k<=C.length; k++) {
if(A[i-1] == B[j-1] && B[j-1] == C[k-1] && A[i-1] == C[k-1]) {
LCS[i][j][k] = LCS[i-1][j-1][k-1] + 1;
}
else {
if (LCS[i - 1][j][k] > LCS[i][j - 1][k]
|| LCS[i - 1][j][k] > LCS[i][j][k - 1])
LCS[i][j][k] = LCS[i - 1][j][k];
else if (LCS[i][j][k - 1] > LCS[i - 1][j][k]
|| LCS[i][j][k - 1] > LCS[i][j - 1][k])
LCS[i][j][k] = LCS[i][j][k - 1];
else
LCS[i][j][k] = LCS[i][j - 1][k];
}
}
}
}
// 정답 출력
System.out.println(LCS[A.length][B.length][C.length]);
}
}
반응형
'PS 문제 풀이 > Baekjoon' 카테고리의 다른 글
[BOJ] 백준 16236 아기상어 (0) | 2021.02.21 |
---|---|
[BOJ] 백준 15683 감시 (0) | 2021.02.21 |
[BOJ] 백준 9252 LCS 2 (0) | 2021.02.21 |
[BOJ] 백준 9251 LCS (0) | 2021.02.21 |
[BOJ] 백준 5582 공통 부분 문자열 (Java) (0) | 2021.02.21 |
댓글