[Algorithm] 99클럽 코테 스터디 23일차 TIL | 백준_LCS(9251번)

📝문제

 

💡풀이

첫 번째로 주어지는 문장을 str1, 두 번째로 주어지는 문장을 str2라고 하자.

 

dp[i][j] 는 str1 문장의 0번째 문자부터 i번째 문자까지의 원소와 str2 문장의 0번째 문자부터 j번째 문자까지의 원소들 가운데 만들 수 있는 최대 공통 수열을  의미한다.

 

str1: ACAYKP

str2: CAPCAK

 

dp[0][0] => {A}, {C} 로 만들 수 있는 최대 공통 수열 => 없음

dp[0][1] => {A}, {C,A} 로 만들 수 있는 최대 공통 수열 => {A}

dp[0][2] => {A}, {C,A,P} 로 만들 수 있는 최대 공통 수열 => {A}

dp[0][3] => {A}, {C,A,P,C} 로 만들 수 있는 최대 공통 수열 => {A}

dp[0][4] => {A}, {C,A,P,C,A} 로 만들 수 있는 최대 공통 수열 => {A}

dp[0][5] => {A}, {C,A,P,C,A,K} 로 만들 수 있는 최대 공통 수열 => {A}

 

표로 나타내면 아래와 같다.

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

 

dp[0][j]와 dp[i][0]은 미리 초기화를 해주었다.

 

이후 str1.charAt(i)와 str2.charAt(i) 같다면?

dp[1][3]을 보면 {A,C}와 {C,A,P,C} 로 만들 수 있는 공통 부분 수열이다.

이는 곧 {A}와 {C,A,P}로 만들 수 있는 공통 부분 수열에 C가 추가된 것과 같으므로

dp[i][j] = dp[i-1][j-1] + 1이라는 식을 얻을 수 있다.

 

str1.charAt(i)와 str2.charAt(i) 이 다르다면?

dp[1][4]의 경우를 보자.

{A,C}와 {C,A,P,C,A}로 만들 수 있는 공통 부분 수열은

 

{A}와 {C,A,P,C,A}로 만들 수 있는 공통 부분 수열과

{A,C}와 {C,A,P,C}로 만들 수 있는 공통 부분 수열 중

더 길이가 긴 공통 부분 수열을 채택하는 것과 같다.

 

즉 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])이라는 식을 얻을 수 있다.

 

전체풀이

import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[][] dp = new int[str1.length()][str2.length()];

        int max = 0;
        for(int i = 0; i < str2.length(); i++){
            if(str1.charAt(0) == str2.charAt(i)){
                max = 1;
            }
            dp[0][i] = max;
        }

        max = 0;
        for(int i = 0; i < str1.length(); i++){
            if(str2.charAt(0) == str1.charAt(i)){
                max = 1;
            }
            dp[i][0] = max;
        }

        for(int i = 1; i < str1.length(); i++){
            for(int j = 1; j < str2.length(); j++){
                if(str1.charAt(i) == str2.charAt(j)){
                    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()-1][str2.length()-1]);

    }
}

 

🤔Review

1도 감을 못잡아서 다른 분의 접근 방법을 참고하였다. 다이나믹한 프로그래밍이었다..

https://st-lab.tistory.com/139

[백준] 9251번 : LCS - JAVA [자바]