백준 1958 LCS 3

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

1958번: LCS 3

삼중배열을 이용한 LCS 문제

 

요구하는 알고리즘이 선명한 문제는 상대적으로 쉬운 것 같다.

import java.io.*;

public class Main {

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int LCS(String a, String b, String c) {
        int[][][] common = new int[a.length() + 1][b.length() + 1][c.length() + 1];
        int[][][] dir = new int[a.length() + 1][b.length() + 1][c.length() + 1];

        // 1은 다 1빼기 2는 i 3은 j 4는 k
        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.charAt(i - 1) == b.charAt(j - 1) && b.charAt(j-1) == c.charAt(k-1)) {
                        common[i][j][k] = common[i - 1][j - 1][k - 1] + 1;
                        dir[i][j][k] = 1;
                    } else {
                        common[i][j][k] = Math.max(common[i - 1][j][k], Math.max(common[i][j - 1][k], common[i][j][k - 1]));
                        if (common[i - 1][j][k] > common[i][j - 1][k]) {
                            if (common[i - 1][j][k] > common[i][j][k - 1])
                                dir[i][j][k] = 2;
                            else
                                dir[i][j][k] = 4;

                        } else {
                            if (common[i][j - 1][k] > common[i][j][k - 1])
                                dir[i][j][k] = 3;
                            else
                                dir[i][j][k] = 4;
                        }
                    }
                }
            }
        }

        return common[a.length()][b.length()][c.length()];
    }

    public static void main(String[] args) throws IOException {
        String a, b, c;

        a = br.readLine().trim();
        b = br.readLine().trim();
        c = br.readLine().trim();

        bw.write(LCS(a, b, c) + "\n");
        bw.flush();
    }
}