[BaekJoon] 1958 LCS 3 (Java)

1.  문제 링크

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

2.  문제

요약

• 문자열 3개가 주어졌을 때, 문자열 3개의 LCS를 구하는 문제입니다.
• 과제들의 마감일과 점수가 주어질 때, 웅찬이가 얻을 수 있는 점수의 최댓값을
• 입력: 첫 번째 줄에 첫 번째 문자열이, 두 번째 줄에 두 번째 문자열이, 세 번째 줄에 세 번째 문자열이 주어집니다.
  • 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같습니다.
• 출력: 첫 번째 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static final int SIZE = 3;
    static String[] strings;
    static void input() {
        Reader scanner = new Reader();
        strings = new String[SIZE];
        for(int idx = 0; idx < SIZE; idx++) strings[idx] = scanner.nextLine();
    }

    static void solution() {
        System.out.println(findLCS(strings[0], strings[1], strings[2]));
    }

    static int findLCS(String str1, String str2, String str3) {
        int[][][] dp = new int[str1.length() + 1][str2.length() + 1][str3.length() + 1];
        for(int idx1 = 1; idx1 <= str1.length(); idx1++) {
            char char1 = str1.charAt(idx1 - 1);

            for(int idx2 = 1; idx2 <= str2.length(); idx2++) {
                char char2 = str2.charAt(idx2 - 1);

                for(int idx3 = 1; idx3 <= str3.length(); idx3++) {
                    char char3 = str3.charAt(idx3 - 1);

                    if(char1 == char2 && char2 == char3) {
                        dp[idx1][idx2][idx3] = dp[idx1 - 1][idx2 - 1][idx3 - 1] + 1;
                    } else {
                        dp[idx1][idx2][idx3] = Math.max(dp[idx1 -1][idx2][idx3],
                                Math.max(dp[idx1][idx2 - 1][idx3],
                                dp[idx1][idx2][idx3 - 1]));
                    }
                }
            }
        }
        return dp[str1.length()][str2.length()][str3.length()];
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}