[SW expert Academy] SWEA 3304번 최장 공통 부분 수열 자바(Java)

[D3] 최장 공통 부분 수열 - 3304

문제 링크

성능 요약

메모리: 39,240 KB, 시간: 189 ms, 코드길이: 779 Bytes

제출 일자

2023-11-10 13:31

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

import java.util.Scanner;
class Solution {
	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc = 1; tc <= T; tc++) {
            String a = sc.next();
            String b = sc.next();
            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()]);
		}
	}
}