[백준] 9251 LCS

https://www.acmicpc.net/problem/9251

9251번: LCS

 

Logest Common Subsequence라고 불리는 LCS는 이 LCS 자체를 구하는 방법을 기준으로 해서 문자열 파트에서 꽤 다양하게 응용이 되는 것 같다. 이 부분에 대해 공부를 해야지해야지 하면서 계속 미루다가 오늘 여유가 되서 좀 살펴보았는데 역시 알고리즘은 문제를 해결하기 위해 어떤 방법을 쓰는지가 중요한 것 같다. 방법을 알고나면 알고리즘 자체가 어렵거나 복잡하진 않았다. (참고 티스토리 : https://sskl660.tistory.com/90)

---

문제 및 입출력

---

코드

import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        char[] a = sc.nextLine().toCharArray();
        char[] b = sc.nextLine().toCharArray();
        
        int[][] dp = new int[b.length+1][a.length+1];
        
        for(int i=1; i<=b.length; i++)
        {
         for(int j=1; j<=a.length; j++)
         {
         if(b[i-1]==a[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[b.length][a.length]);
        sc.close();
    }

}