자바 백준 9251번
골드 5
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
문제 보기

분류: 다이나믹 프로그래밍, 문자열
코드 풀이
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 두 문자열 입력 String str1 = sc.nextLine(); String str2 = sc.nextLine(); // LCSCalculator 객체 생성 LCSCalculator lcsCalculator = new LCSCalculator(); // LCS 길이 계산 int lcsLength = lcsCalculator.calculateLCSLength(str1, str2); // 계산된 LCS의 길이 출력 System.out.println(lcsLength); } } class LCSCalculator { // LCS 길이를 계산하는 메서드 public int calculateLCSLength(String str1, String str2) { // 각 문자열의 길이 구하기 int m = str1.length(); int n = str2.length(); // DP 테이블 초기화 int[][] dp = new int[m + 1][n + 1]; // 다이나믹 프로그래밍을 통해 LCS 길이 계산 // dp[i][j]는 문자열 str1의 처음부터 i번째 문자까지, 그리고 문자열 str2의 처음부터 j번째 문자까지의 LCS 길이를 나타냄 // 문자열 str1의 각 문자를 순회 for (int i = 1; i <= m; i++) { // 문자열 str2의 각 문자를 순회 for (int j = 1; j <= n; j++) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) // 이전까지의 LCS 길이에 현재 문자를 추가하면서 LCS의 길이를 증가 dp[i][j] = dp[i - 1][j - 1] + 1; else // 현재 비교하는 문자가 다르다면, 이전까지의 LCS 중 최대값을 선택하여 현재 위치의 LCS 길이를 결정 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } // 계산된 LCS의 길이 반환 return dp[m][n]; } }
'공부하기 > 백준' 카테고리의 다른 글
[Java] 백준 풀기 15815 - 천재 수학자 성필 (0) | 2024.04.07 |
---|---|
[Java] 백준 풀기 23037 - 5의 수난 (0) | 2024.04.06 |
[Java] 백준 풀기 4358 - 생태학 (0) | 2024.04.04 |
[Java] 백준 풀기 1094 - 막대기 (0) | 2024.04.02 |
[Java] 백준 풀기 5397 - 키로거 (0) | 2024.04.01 |