LCS(Longest Common Subsequence) 알고리즘 (C), 백준 1958 LCS3(JAVA)

이전 글

 

2020/07/10 - [공부] - LCS(Longest Common Subsequence) 알고리즘 (B), 백준 9252 LCS2

LCS(Longest Common Subsequence) 알고리즘 (B), 백준 9252 LCS2

에 이어서, 백준 1958 LCS3 문제를 풀어보겠습니다.

 

 

 

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

1958번: LCS 3

백준 1958 - "LCS 3"

 

이번 문제는 "백준 - LCS2"와 다르지 않습니다. 다만, 문자열이 2개가 아닌 3개라는 것이 다를 뿐...

 

문자열이 2개든, 3개든 10개든 사용하는 논리는 다르지 않습니다.

 

- 경우1) "A[i] = B[j] = C[k]" 인 상황

- 경우2) "경우 1)"이 아닌 모든 상황

 

이라고 보면 됩니다.

 

- 첫 번째 경우는 기존의 LCS와 같습니다.

- 두 번째 경우는, 기존의 max(DP[i - 1][j], DP[i][j - 1])를 변형시키면 됩니다.

 DP[i][j][k] = max(DP[i - 1][j][k], DP[i][j - 1][k], DP[i][j][k - 1])

 

끝)

 

코드 - JAVA

import java.io.*;
public class Main {
    private static int max(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        char[] str3 = br.readLine().toCharArray();
        
        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[i - 1] == str2[j - 1] && str2[j - 1] == str3[k - 1]) {
                        dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
                    } else {
                        dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1]);
                    }
                }
            }
        }
        System.out.print(dp[str1.length][str2.length][str3.length]);
    }
}
 

 

다음글

2020/07/10 - [공부] - LCS(Longest Common Subsequence) 알고리즘 (D), 백준 13711 LCS4(JAVA)

LCS(Longest Common Subsequence) 알고리즘 (D), 백준 13711 LCS4(JAVA)