3304. 최장 공통 부분 수열

문제 출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOHEx66kIDFAWr

최장 공통 부분 수열 개념을 코딩으로 짜면 됩니다.

2018년 3월 27일 import java.util.Scanner; public class Q3304 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int testCase = sc.nextInt(); for (int i = 1; i <= testCase; i++) { int result = 0; String firstString = sc.next(); String secondString = sc.next(); int[][] resultArray = new int[secondString.length()+1][firstString.length()+1]; for (int j = 0; j < secondString.length(); j++) { for (int k = 0; k < firstString.length(); k++) { if (secondString.charAt(j) == firstString.charAt(k)) { int value = resultArray[j][k]+1; resultArray[j+1][k+1] = value; if (result < value) { result = value; } } else { int left = resultArray[j+1][k]; int up = resultArray[j][k+1]; resultArray[j+1][k+1] = Math.max(left, up); } } } System.out.println("#" + i + " " + result); // 출력 // System.out.print("    "); // for (int k = 0; k < firstString.length(); k++) { // System.out.print(firstChars[k] + " "); // } // System.out.println(); // for (int j = 0; j <= secondString.length(); j++) { // if (j == 0) { // System.out.print("  "); // } else { // System.out.print(secondChars[j-1] + " "); // } // for (int k = 0; k <= firstString.length(); k++) { // System.out.print(resultArray[j][k] + " "); // } // System.out.println(); // } } } }