BOJ 9251 LCS

1. 변수

   String S1, S2 // 문자열 입력받기
   int[][] dp = new int[S1.length()+1][S2.length()+1];
   

2. 구현로직

   1. dp와 이차원배열을 활용했다

   (*) Youtube Link

   => 이 영상 보면 한번에 이해됨!

3. 코드

   package baekjoon.Gold;
      
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
      
   public class BOJ_9251_LCS {
   	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[S1.length() + 1][S2.length() + 1];
      
   		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)) {
   					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[S1.length()][S2.length()]);
      
   	}
   }
      
   

문제 링크 : 백준 9251 LCS