[SWEA] 최장 공통 부분 수열

 

 

[문제]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOHEx66kIDFAWr

SW Expert Academy

 

 

 

[소스 코드]

import java.io.*;
import java.util.*;
public class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for(int tc=1;tc<=T;tc++) {
			st = new StringTokenizer(br.readLine());
			String a = st.nextToken();
			String b = st.nextToken();
			int[][] dp = new int[a.length()+1][b.length()+1];
			for(int i=1;i<=a.length();i++) {
				for(int j=1;j<=b.length();j++) {
					if(a.charAt(i-1)==b.charAt(j-1)) {
						dp[i][j] = dp[i-1][j-1] + 1;
					}
					else
						dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
				}
			}
			System.out.println("#"+tc+" "+dp[a.length()][b.length()]);
		}
	}
}