bj1958 LCS3 (최장 공통 부분 수열)

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

 

이 문제는 LCS의 개념만 제대로 알면 매우 쉽게 풀 수 있다.

 

만약, 3중 for문을 돌려, 3개의 값이 다 같다면

dp[y][x][z] = dp[y-1][x-1][z-1] + 1

을 해준다.

 

-> 다 같은 임의의 인덱스가 a,b,c라 하면

a-1, b-1, c-1까지의 최장 공통 부분 수열에 a,b,c에 해당하는 값을 더해주면 되기 때문.

 

만약, 3중 for문을 돌려, 3개의 값 중 하나라도 틀리다면

dp[y][x][z] = findMax(dp[y-1][x][z], dp[y][x-1][z], dp[y][x][z-1]);

을 해준다.

-> 하나라도 틀리다면, 현재 인덱스까지의 최장 공통 부분 수열은 

(y-1,x,z), (y,x-1,z), (y,x,z-1) 중 하나가 될 것이기 때문.

 

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

public class Main {
    static String[] strings;
    static int[][][] dp;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        strings = new String[3];
        for(int i = 0; i < 3; i++){
            strings[i] = bufferedReader.readLine();
        }
        dp = new int[ strings[0].length() + 1 ][ strings[1].length() + 1 ][ strings[2].length() + 1 ];

        int ans = 0;
        for(int y = 1; y <= strings[0].length(); y++){
            for(int x = 1; x <= strings[1].length(); x++){
                for(int z = 1; z <= strings[2].length(); z++){
                    if(strings[0].charAt(y-1) == strings[1].charAt(x-1) && strings[1].charAt(x-1) == strings[2].charAt(z-1)){
                        dp[y][x][z] = dp[y-1][x-1][z-1] + 1;
                        ans = Math.max(ans, dp[y][x][z]);
                    }else{
                        dp[y][x][z] = findMax(dp[y-1][x][z], dp[y][x-1][z], dp[y][x][z-1]);
                    }
                }
            }
        }
        System.out.println(ans);
    }

    private static int findMax(int a, int b, int c) {
        int[] arr = new int[3];
        arr[0] = a;
        arr[1] = b;
        arr[2] = c;
        Arrays.sort(arr);
        return arr[2];
    }
}