BOJ - 9251 ) LCS

개발자가될수있을까? 2020. 8. 25. 12:25

https://www.acmicpc.net/problem/9251

9251번: LCS

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

www.acmicpc.net

최장 공통 부분 수열을 구하기 위해 이전까지의 최장 공통 부분 수열을 구해 놓는다.

현재 문자가 격자상 문자와 같으면 대각선의 값 + 1을 현재 값으로,

다르다면 위 아래중 큰값으로 따라간다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class LCS {

	public static void main(String[] args) throws Exception {
	
		BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
		String strA = br.readLine();
		String strB = br.readLine();
		int map[][] = new int[strA.length()+1][strB.length()+1];
		for(int i = 1 ; i < strA.length()+1 ; i++) {
			for(int j = 1 ; j < strB.length()+1 ; j++) {
				if(  strA.charAt(i-1) ==	 strB.charAt(j-1)  ) {
					map[i][j] = map[i-1][j-1]+1;
				} else {
					map[i][j] = max(map[i-1][j], map[i][j-1]);
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append(map[strA.length()][strB.length()] + "\n");
		System.out.println(sb);
	
	}

	private static int max(int i, int j) {
		return i = i > j ? i : j ;
	}
}