[BOJ/백준] 9251: LCS

9251번: LCS
- 문제 내용
- 코드
맺음

이번 글에서는 백준 알고리즘 사이트의 9251번 LCS 문제 풀이와 어떤 문제였는지 정리해보는 시간을 가져보겠습니다.

9251번: LCS

문제는 위 링크를 통해서 확인하실 수 있습니다.

문제 내용

LCS (Longest Common Subsequence)의 뜻은 최장 공통 부분수열을 의미합니다. 이 문제에서 요구하는 것은 두 배열이 주어졌을 때, 두 배열 모두에 포함되는 부분 수열 중 가장 긴 수열을 찾는 것입니다.

문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

코드

import java.io.*;

public class B9251 {
    static String s1, s2;
    static int[][] lcs = new int[1001][1001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        s1 = br.readLine();s2 = br.readLine();
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.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]);
            }
        }
        bw.write(lcs[s1.length()][s2.length()] + "\n");
        bw.flush();bw.close();
    }
}

맺음

간단하게 9251번: LCS 문제 풀이를 해보았습니다. 혹시 궁금하신 점이나 이상한 점이 있으시면 댓글 부탁드리겠습니다.

감사합니다.

#9251번 LCS,
#BOJ,
#BOJ 9251,
#백준,
#백준 9251

글이 도움이 되셨다면, 커피 한 잔만 사주세요!

Comments

Copied to clipboard

[BOJ/백준] 9251: LCS

Table of Contents

9251번: LCS

문제 내용

코드

맺음