SWEA 3304 최장 공통 부분 수열

1 개요

SWEA 3304 최장 공통 부분 수열

SW Expert 아카데미

#	문제	풀이

3 Java

import java.util.*;
public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			char[] X = sc.next().toCharArray();
			char[] Y = sc.next().toCharArray();
			int m = X.length;
			int n = Y.length;
			int a[][] = new int[m+1][n+1];
			for(int i=0; i<=m; i++) {
				for(int j=0; j<=n; j++) {
					if( i==0 || j==0 ) {
						a[i][j] = 0;
						continue;
					}
					if( X[i-1] == Y[j-1] ) {
						a[i][j] = a[i-1][j-1]+1;
						continue;
					}
					a[i][j] = Math.max(a[i-1][j],a[i][j-1]);
				}
			}
			System.out.format("#%d %d\n",tc, a[m][n]);
		}
		sc.close();
	}
}

4 같이 보기

• 최장 공통 부분수열