[BOJ] 9251. LCS

[작성일]

• 2022-03-23

[분류]

• dp
• LCS
  
  
  

[문제링크]

• https://www.acmicpc.net/problem/9251
  
  
  

[요구사항]

LCS를 구하라.

[풀이]

LCS 알고리즘을 구현하는 문제이다.
dp 2차원 배열을 사용하는 문제이다.

각 문자열들의 문자들을 서로 비교하면서 서로 같으면 1씩 증가시키면서 누적합을 구한다.
문자열 A를 기준으로 시작한다.
A의 1번째 문자를 기준으로 B와 얼마나 공통될 수 있는지 살펴보며 dp를 채워나간다.
이것을 A 마지막 문자까지 반복한다.

dp 값을 갱신하는 경우는 다음과 같다.

• 바로 앞 글자가 같을 경우에는 1씩 늘려줘야하기 때문에 dp[i][j] = dp[i-1][j-1] + 1
• 그렇지 않은 경우 이전 행 또는 열 원소 중 큰 것으로 갱신한다.
  
  
  

[코드 - Bottom-Up]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


class Main {
    static int[][] LCS;
    static String A, B;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        A = br.readLine();
        B = br.readLine();
        LCS = new int[A.length() + 1][B.length() + 1];

        System.out.println(getLCSLen());
    }

    public static int getLCSLen() {
        for (int i = 1; i <= A.length(); i++) {
            for (int j = 1; j <= B.length(); j++) {
                if (A.charAt(i - 1) == B.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]);
                }
            }
        }
        return LCS[A.length()][B.length()];
    }
}

[코드 - Top-Down]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


class Main {
    static Integer[][] LCS;
    static String A, B;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        A = br.readLine();
        B = br.readLine();
        LCS = new Integer[A.length()][B.length()];

        System.out.println(getLCSLen(A.length() - 1, B.length() - 1));
    }

    public static int getLCSLen(int i, int j) {
        if (i == -1 || j == -1) {
            return 0;
        }

        if (LCS[i][j] == null) {
            LCS[i][j] = 0;

            if (A.charAt(i) == B.charAt(j)) {
                LCS[i][j] = getLCSLen(i - 1, j - 1) + 1;
            } else {
                LCS[i][j] = Math.max(getLCSLen(i - 1, j), getLCSLen(i, j - 1));
            }
        }

        return LCS[i][j];
    }
}