[JAVA43] 9251. LCS

9251. LCS (G5)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.1 초	256 MB	94234	39280	28794	41.036 %

 

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

---

summary

•  두 문자열의 LCS의 길이를 출력 ( Longest Common Subsequence, 최장 공통 부분 수열)

 

strategy

DP 활용 (완전 탐색 시간 초과)

 

• 배열의 매 인덱스는 최대값으로 갱신
• 현재 비교 단어가 같다면 직전 단어에서 제일 최신값에서 1 더함 (DP[i-1][j-1] + 1)
• 현재 비교 단어가 다르다면 이전 단어들 중 제일 최신값 중 최대값 가져오기 (Math.max(DP[i-1][j], DP[i][j-1])

 

note

• 알파벳 대문자로 구성
• 최대 1000글자

import java.util.*;
import java.io.*;

public class Main {

    static String str1, str2;
    static int[][] DP;
    
    public static void main(String[] args) throws IOException {    

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        str1 = br.readLine();
        str2 = br.readLine();

        DP = new int[str1.length() + 1][str2.length() + 1]; // 0행, 0열은 indexError 방지용. (1,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-1][j], DP[i][j-1]);
                }
            }
        }

        System.out.println(DP[str1.length()][str2.length()]);
    }
}

 

문제	결과	메모리	시간	언어코드	길이
9251	맞았습니다!!	18528 KB	132 ms	Java 11 / 수정	870 B

 

 

memo

• DP는 비슷한 풀이 양상을 띠기 때문에 많은 문제를 풀어서 감을 익혀야 할듯

 

• 예시를 통한 설명은 다음 블로그 참고

[Java] 백준 9251번: LCS