[백준 1958] LCS 3(Java)

문제 링크 : https://www.acmicpc.net/problem/1958

이 문제는 dp를 이용하여 풀 수 있습니다.

공통 문자를 구하는 방법은 다음과 같습니다.

1. 첫 번째 문자의 i번째 문자와 두 번째 문자의 j번째 문자, 세 번째 문자의 k번째 문자가 모두 같고 각각의 전 문자들 역시 모두 같다면 dp[i][j][k] = dp[i-1][j-1][k-1]+1
2. 그렇지 않다면 dp[i][j][k] = Math.max(dp[i - 1][j][k], Math.max(dp[i][j - 1][k], dp[i][j][k - 1]));

원리는 단순합니다. 각각의 인덱스의 문자가 같고 그 이전도 같다면 dp값을 증가시켜주고, 그렇지 않다면 이전 dp값 중 최댓값을 가져오게 되면 dp의 가장 끝 값에 최댓값이 저장됩니다. 이를 리턴하면 됩니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String first = br.readLine();
        String second = br.readLine();
        String third = br.readLine();

        int[][][] dp = new int[first.length() + 1][second.length() + 1][third.length() + 1];

        for (int i=1;i<=first.length();i++){
            for (int j=1;j<=second.length();j++){
                for (int k=1;k<=third.length();k++){
                    if (first.charAt(i - 1) == second.charAt(j - 1) && second.charAt(j - 1) == third.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[first.length()][second.length()][third.length()]);
    }
}