본문 바로가기
PS 문제 풀이/Baekjoon

[BOJ] 백준 1958 LCS 3

by 까망 하르방 2021. 2. 21.
반응형

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

 Input 

abcdefghijklmn

bdefg

efg

  

 Output 

3

두 문자열을 입력받아 LCS를 출력하는 문제

LCS (Longest Common Subsequence) 알고리즘

 

LCS(Longest Common Subsequence) 알고리즘

LCS(Longest Common Subsequence) '최장 공통 부분 수열'로 연속된 부분 문자열 Substring과는 다른 개념이다.   ▶ [BOJ] 5582 공통 부분 문자열 가령, 아래 두 문자열이 주어졌을 때, - A   B   C   D..

zoosso.tistory.com

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

댓글