99클럽 코테 스터디 34일차 TIL [LCS -> DP]

 

- 오늘의 학습 키워드 : LCS(DP 활용)

[문제 이름 : LCS 3 (백준 1958, G4)]
문제 url : https://www.acmicpc.net/problem/1958

내가 작성한 코드는 아래와 같다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str1 = br.readLine();
        String str2 = br.readLine();
        String str3 = br.readLine();

        int n = str1.length();
        int m = str2.length();
        int l = str3.length();

        // DP 배열 생성
        int[][][] dp = new int[n + 1][m + 1][l + 1];

        // DP 점화식 구현
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 1; k <= l; k++) {
                    if (str1.charAt(i - 1) == str2.charAt(j - 1) && str2.charAt(j - 1) == str3.charAt(k - 1)) {
                        dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
                    } else {
                        dp[i][j][k] = Math.max(Math.max(dp[i - 1][j][k], dp[i][j - 1][k]), dp[i][j][k - 1]);
                    }
                }
            }
        }

        // 최종 결과 출력
        System.out.println(dp[n][m][l]);
    }
}

풀이 과정(풀이 시간 : 1시간)

LCS 문제는 봐도봐도 익숙해지지가 않는 것 같다. 아래 블로그를 자주 참고하며 개념을 복습하고는 하는데, 이번에도 블로그를 참고하게 되었다. ㅠㅠ ( 링크:  https://lotuslee.tistory.com/39?category=964787 )

1. 기존 LCS가 2개의 문자열을 비교하는 것이라면, 이번에는 3개의 문자열을 비교하게 되므로 DP의 풀이법에 3번의 중첩 for문이 들어가게 된다.

2. Subsequence가 성립하는 경우, dp대각선 위값에 +1한 값을 저장한다.

3. Subsequence가 성립하지 않는 경우, 왼쪽, 위의 값 중 최댓값을 가져온다.

4. 최종 LCS가 될 수 있는 값의 길이를 구한다.

내일은 은행 인턴 자기소개서를 작성할 예정이다.

[참고 블로그]

LCS(Longest Common Subsequence)