[백준] 9251번(Java)

📖 LCS

[ 문제 ]
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

💡풀이

• 2차원 배열로 풀이
• 문자열1과 문자열2의 각 문자들을 하나씩 비교 -> 일치하는 경우 현재 위치에서 행-1, 열-1 위치의 값에 1을 추가한 값을 더함
• 일치하지 않는 경우, 행-1위치의 값과 열-1 위치의 값 중 큰 값을 현재 위치의 값으로 결정
• 필자는 2차원 배열 없이 덤볐다가 호되게 당하고 다시 수정해서 품. 더 좋은 방법 있을 것 같은데...
  

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String str1 = br.readLine();
        String str2 = br.readLine();
        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.charAt(i - 1) == str2.charAt(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()]);
    }
}

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