[백준] 9251번: LCS

이 문제는 문자열을 문자배열로 변환해서 한 글자씩 검사하면 된다.

우선 dp[i][j]를 부분 문자열s1(0,i) 와 s2(0,j) 의 LCS라고 정하면 규칙은 다음과 같당

if(s1[i] == s2[j]) { // 글자가 동일하면 +1
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 1;
} else { // 아니면 이전 글자 까지의 LCS
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}

예제를 손으로 풀어보면 다음 그림처럼 된다.

이 때 손으로 푼 것처럼 반복문을 돌리려면 배열 크기를 +1 씩 해줘야한다🥴

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

public class boj9251 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        char[] str1 = in.readLine().toCharArray();
        char[] str2 = in.readLine().toCharArray();
        int[][] dp = new int[str1.length+1][str2.length+1];
        for(int i = 1; i <= str1.length; i++){
           for(int j = 1; j <= str2.length; j++){
               if(str1[i-1] == str2[j-1]) {
                   dp[i][j] = dp[i-1][j-1] + 1;
               } else {
                   dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
               }
           }
        }
        System.out.println(dp[str1.length][str2.length]);
    }
}