[BOJ] 9251 -LCS(G5)

suhyun·2022년 12월 1일
0

백준/프로그래머스

목록 보기
42/81

문제 링크

9251-LCS


입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 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()]);
    }
}
profile
꾸준히 하려고 노력하는 편 💻

0개의 댓글