acmicpc

[BAEKJOON] 9251. LCS

코드와이 2021. 4. 27. 00:30

 

문제링크

www.acmicpc.net/problem/9251

 

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

 

package acmicpc.Gold5;

import java.util.Scanner;

public class LCS {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String str1 = sc.next();
		String str2 = sc.next();
		
		int[][] lcs = new int[str1.length() + 1][str2.length() + 1];
		for(int i = 1 ; i <= str1.length() ; i++) {
			for(int j = 1 ; j <= str2.length() ; j++) {
				if(str1.charAt(i-1) == str2.charAt(j-1)) {
					lcs[i][j] = lcs[i-1][j-1] + 1;
				} else {
					lcs[i][j] = Math.max(lcs[i][j-1], lcs[i-1][j]);
				}
			}
		}
		System.out.println(lcs[str1.length()][str2.length()]);
	}
}