백준 9251 LCS

백준 9251 LCS

---

오늘은 대표적인 LCS 문제를 풀어보았다. 예전에 해본적이 있었는데 가물가물해서 시간이 좀 걸렸다.

LCS 의 경우 2차원 배열을 만들어 점화식을 직접 만들어보면 된다.

• 두 문자열에서 참조하고 있는 부분이 같은 경우
  • table[i][j] = table[i-1][j-1] + 1
• 서로 다른 경우
  • max(table[i-1][j], table[i][j-1]);

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1, s2;
        s1 = scanner.nextLine();
        s2 = scanner.nextLine();
        int table[][] = new int[1002][1002];

        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)) {
                    table[i][j] = table[i - 1][j - 1] + 1;
                } else {
                    table[i][j] = Integer.max(table[i-1][j], table[i][j-1]);
                }
            }
        }
        System.out.println(table[s1.length()][s2.length()]);
    }