Baekjoon Online Judge

algorithm practice

-問題を逐次解く

27.動的計画法と最短距離逆追跡

4. LCS 2

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

public class Main {  
	static char[] arr1, arr2;
	static int[][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
		StringBuilder sb = new StringBuilder();
        
		arr1 = br.readLine().toCharArray(); 
		arr2 = br.readLine().toCharArray(); 
        
		int len1 = arr1.length;
		int len2 = arr2.length;        
        
		dp = new int[len1 + 1][len2 + 1];
        
		for(int i = 0; i < len1; i++) {
			for(int j = 0; j < len2; j++){
				if(arr1[i] == arr2[j]) { 
					dp[i+1][j+1] = dp[i][j]+1;
				} else{ 
					dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]); 
				} 
			}
		}

		bw.write(dp[len1][len2] + "\n");  
		
		Stack<Character> stack = new Stack<>();
		while(len1 >= 1 && len2 >= 1) {
			if(dp[len1][len2] == dp[len1-1][len2]) { // 위
				len1--; 
			} else if(dp[len1][len2] == dp[len1][len2-1]) { // 왼 
				len2--; 
			} else { // 대각선
				stack.push(arr1[len1 - 1]);
				len1--;
				len2--;
			}
		}
        
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
        
		bw.write(sb.toString());        
		bw.flush();
		br.close();
		bw.close();
	}	
}

import sys
from bisect import bisect_left

arr1 = [0] + list(sys.stdin.readline().strip())
arr2 = [0] + list(sys.stdin.readline().strip())

len1 = len(arr1)
len2 = len(arr2)

dp = [[""] * len2 for _ in range(len1)]

for i in range(1, len1):
    for j in range(1, len2):
        if arr1[i] == arr2[j]:
            dp[i][j] = dp[i - 1][j - 1] + arr1[i]
        else:
            if len(dp[i - 1][j]) > len(dp[i][j - 1]):
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i][j - 1]

print(len(dp[len1 - 1][len2 - 1]))
print(dp[len1 - 1][len2 - 1])