BOJ 9251 LCS

1. 변수

   int[][] dp; //lcs 길이를 담는 배열
   char[] str1; // 문자열1
   char[] str2; // 문자열2
   

2. 로직

   • 문자열 2의 첫글자를 문자열1 모든글자와 비교해서 겹치면 1로 변경

   • 다음 글자를 보면서 dp[i-1] [j], dp[i] [j-1]; 중 큰 값

3. 코드

package com.ssafy;

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

public class BOJ_9251_LCS_210107 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		char[] str1 = br.readLine().toCharArray();
		char[] str2 = br.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-1][j],dp[i][j-1]);
				}
			}
		}
		
		System.out.println(dp[str1.length][str2.length]);
		
	}

}