백준 9251번 : LCS[java]

1. 첫 번째 문자열(s1)과 두 번째 문자열(s2)를 입력받는다.

 

2. dp에 사용할 배열 dp[1001][1001]을 만든다.

ㄴ dp[i][j]는 s1의 i번째와 s2의 j번째 문자까지 비교했을 때 최장 공통 부분수열이다.

 

3. s1의  i번째 문자와 s2의 j번째 문자를 비교하고 같다면 dp[i][j] = dp[i-1][j-1] +1 이고,

→ s1의 i번째 문자와  s2의 j번째 문자를 이번 dp[i][j]에서 공통 문자로 사용했기 때문에 직전까지의 최댓값에 +1을 한다.

 

4. s1의  i번째 문자와 s2의 j번째 문자를 비교하고 다르다면 dp[i][j] = max(dp[i-1][j] , dp[i][j-1]) 이다.

→ i번째 문자와 j번째 문자가 다르기 때문에 직전 문자열에 각각 추가하여 비교한 최댓값이 dp[i][j]가 된다.

 

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();
        
        int[][] dp = new int[1002][1002];
        
        for(int i=0; i<s1.length(); i++) {
        	for(int j=0; j<s2.length(); j++) {
        		if(s1.charAt(i) == s2.charAt(j)) {
        			dp[i+1][j+1] = dp[i][j] + 1;
        		}
        		else {
        			dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
        		}
        	}
        }
        System.out.print(dp[s1.length()][s2.length()]);
    }
}