백준 - LCS

코드

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        
        int[][] dp = new int[s1.length()+1][s2.length()+1];

        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                dp[i][j] = s1.charAt(i - 1) == s2.charAt(j - 1) ?
                        dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        System.out.println(dp[s1.length()][s2.length()]);
    }
}

풀이

1. 먼저, Scanner를 사용하여 두 개의 문자열 s1과 s2를 입력받습니다.

2. 2차원 배열 dp를 초기화합니다. 이 배열은 문자열 s1과 s2의 LCS를 계산하는 데 사용됩니다. dp[i][j]는 s1의 처음 i개 문자와 s2의 처음 j개 문자에 대한 LCS의 길이를 나타냅니다.

3. 중첩된 반복문을 사용하여 dp 배열을 채웁니다. 문자열의 각 문자를 비교하고, 현재 문자가 서로 일치하면 이전 대각선 위치의 LCS 길이에 1을 더하고, 일치하지 않으면 왼쪽 또는 위쪽 값 중 더 큰 값을 선택하여 현재 위치의 LCS 길이를 갱신합니다.

4. 마지막으로, dp 배열의 마지막 값인 dp[s1.length()][s2.length()]를 출력하여 s1과 s2의 LCS 길이를 표시합니다.

참고 LCS

아래 표는 입력 문자열 s1과 s2의 LCS를 계산하는 과정을 보여줍니다.
표의 각 셀은 dp[i][j] 값을 나타내며, 각 단계에서 i와 j는 문자열의 인덱스를 나타냅니다. 첫 번째 문자열 s1의 길이가 m, 두 번째 문자열 s2의 길이가 n이라고 가정합니다.

표

dp[i][j]		a	b	c	d
	0	0	0	0	0
a	0	1	1	1	1
c	0	1	1	2	2
e	0	1	1	2	2
f	0	1	1	2	2

각 셀은 다음과 같은 방식으로 계산됩니다:

1. (0, 0) 위치는 초기화 값으로 0입니다.

2. (1, 1) 위치에서, s1.charAt(0)와 s2.charAt(0)를 비교합니다. 두 문자가 같으므로 이전 대각선 위치 (0, 0)의 값에 1을 더한 값인 1이 됩니다.

3. 다를 경우 dp[i-1][j], dp[i][j-1] 중 큰 값을 선택합니다. 예를 들어, (2, 4) 위치에서 s1.charAt(1)과 s2.charAt(3)을 비교하면 두 문자가 같지 않으므로 dp[i-1][j], dp[i][j-1] 중 큰 값인 2가 선택됩니다.

4. 최종 결과인 dp[m][n]는 s1과 s2의 LCS 길이를 나타냅니다. 이 예제에서는 2가 됩니다.

출처 : 백준 - 9251번