<Algorithm> 68. 9251번 LCS (DP)

1. 9251번 LCS

• 심화 DP 문제, LCS는 두 문자열을 비교하여 겹치지 않아도 만들 수 있는 문자열을 뜻한다. 

• 처음에 힌트를 보고 0 0 배열 부터 시작을 했는데 0번 배열에 0을 넣는 것이 알고리즘에서 필요하구나라는 것을 느꼈다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        String N = br.readLine();
        String M = br.readLine();
        String std[] = new String[N.length()+1];
        String comp[] = new String[M.length()+1];
        int dp[][] = new int[1001][1001];
        
        for(int i = 1; i < N.length() + 1; i ++) {
                std[i] = N.charAt(i-1)+"";
                //가로
        }
        
        for(int i = 1; i < M.length() + 1; i ++) {
                comp[i] = M.charAt(i-1)+"";
                // 세로
        }
        System.out.println(Arrays.toString(std));
        System.out.println(Arrays.toString(comp));
        /*if(std.length > comp.length) {
            String temp_comp[] = comp.clone();
            String temp_std[] = std.clone();
            comp = temp_std;
            std = temp_comp;
        }*/
            
        /*
         *   
         */
        for(int i = 1; i < M.length() + 1; i ++) { // 세로
            for(int j = 1; j < N.length() + 1; j++) { // 가로
                    if(comp[i].equals(std[j])) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }else {
                        dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                    }
                }
            }
        /*
         *   0 A A A
         * 0 0 0 0 0
         * A 0 1 1 
         * A 0
         */
        
        System.out.println(dp[M.length()][N.length()]);
    }
}
/*import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        String N = br.readLine();
        String M = br.readLine();
        String std[] = new String[N.length()];
        String comp[] = new String[M.length()];
        int dp[][] = new int[6][6];
        
        for(int i = 0; i < N.length(); i ++) {
                std[i] = N.charAt(i)+"";
                //가로
        }
        
        for(int i = 0; i < M.length(); i ++) {
                comp[i] = M.charAt(i)+"";
                // 세로
        }
        
        if(std.length > comp.length) {
            String temp_comp[] = comp.clone();
            String temp_std[] = std.clone();
            comp = temp_std;
            std = temp_comp;
        }
        
        if(comp[0].equals(std[0])) {
            dp[0][0] = 1;
        }
        //comp 세로 std 가로 
         for(int j = 1; j < N.length(); j++) {
                if(comp[0].equals(std[j])) {  
                    dp[0][j] = 1;
                }else {
                    dp[0][j] = dp[0][j-1];
                }
                
                    A C A Y K P     
                 *  C 0 1 1 1 1 1
                 *  A 1 1 2 2 2 2
                 *  P 1 1 2 2 2 3
                 *  A
                 *    A A A
                 *  A 1 1 1
                 *  A 1 2 2
                 * 
            }
         
        for(int i = 1; i < M.length(); i ++) { // 세로
            for(int j = 0; j < N.length(); j++) { // 가로
                if(j == 0) {
                    if(comp[i].equals(std[j])) {
                        dp[i][j] = dp[i - 1][j] + 1;
                    }else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }else {
                    if(comp[i].equals(std[j])) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        //dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + 1;
                    }else {
                        dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                    }
                }
            }
        }
        System.out.println(Arrays.deepToString(dp));
        
         *   0  A  C  A  Y  K  P
         * 0 0  0  0  0  0  0  0   
         * C 0  0  1  1  1  1  1    C  -  AC
         * A 0  1  1  2  2  2  2    CA - ACA
         * P 0  
         * C 0  
         * A 0  
         * K 0 
         
        System.out.println(dp[M.length()-1][N.length()-1]);
    }
}*/

참고 & 출처  http://twinw.tistory.com/126