첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
LCS 알고리즘 대표 문제
LCS 알고리즘은 공통 부분 문자열 중 가장 길이가 긴 문자열을 찾는 알고리즘이다. ( 링크 참고 )
lcs 알고리즘에 대해서 이해한 뒤 풀이했는데
기본적으로 dp를 기반으로 한 풀이였다.
어렵진 않았고 새로운 알고리즘 알게돼서 한 번 정리하고 넘어갈 수 있었다.
lcs에는 top-down
방식과 bottom-up
방식이 있는데
나는bottom-up
방식을 이용했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[][] lcs;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
String s1 = st.nextToken();
st = new StringTokenizer(br.readLine());
String s2 = st.nextToken();
lcs = new int[s2.length() + 1][s1.length() + 1];
for (int i = 1; i <= s2.length(); i++) {
for (int j = 1; j <= s1.length(); j++) {
if (s2.charAt(i - 1) == s1.charAt(j - 1)) {
lcs[i][j] = lcs[i - 1][j - 1] + 1;
} else {
lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
}
}
}
System.out.println(lcs[s2.length()][s1.length()]);
}
}