[백준][DP] 9251 LCS 알고리즘

LCS(Longest Common Subsequence)는 다이나믹 프로그래밍을 이용한 알고리즘 문제 풀이에 자주 이용된다. 

이는 문자열 두개를 비교하여 순서대로 있는 가장 긴 문자의 수를 세는 것이다. 

배열을 만들어서 문자가 일치할 때는 좌측 상단의 값에 +1을 하여 주고, 

일치 하지 않으면 좌측 또는 상단의 값 중 더 큰값을 선택하여 준다. 

이를 끝까지 반복하여 나오는 가장 큰 수가 LCS 값이 된다. 

import java.util.Scanner;

public class Problem9251 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String str1 = sc.nextLine();

String str2 = sc.nextLine();

sc.close();

int[][] dp = new int[str1.length() + 1][str2.length() + 1];

for (int x = 1; x <= str1.length(); x++) {

char c1 = str1.charAt(x - 1);

for (int y = 1; y <= str2.length(); y++) {

char c2 = str2.charAt(y - 1);

if (c1 == c2) {

// 값이 같으면 좌측 대각선 위의 값 + 1

dp[x][y] = dp[x - 1][y - 1] + 1;

} else {

// 값이 다르면 좌측(x-1), 상단(y-1)의 값중 더 큰 값

dp[x][y] = Math.max(dp[x - 1][y], dp[x][y - 1]);

}

}

}

System.out.println(dp[str1.length()][str2.length()]);

}

}

http://twinw.tistory.com/126

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