[BOJ] 5582. 공통 부분 문자열

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

접근 방법

먼저 2개의 문자열에 대해 완전탐색을 하기로 결정함.

하지만 그렇게 하게 되면 N! 이 나오기 때문에 메모이제이션을 하기로 결정했다.

처음에 코드를 구현 할 때 나는 재귀적으로 풀어주려고 했었다.

static int recursive(int char1_index,int char2_index ){
        if(char1_index >= char1.size() || char2_index >= char2.size()){
            return 0;
        }
        if(dp[char1_index][char2_index]!=0){
            return dp[char1_index][char2_index];
        }
        dp[char1_index][char2_index] = 1;
        if(char1.get(char1_index) == char2.get(char2_index)){
            dp[char1_index][char2_index] += recursive(char1_index+1,char2_index+1);
        }else{
            dp[char1_index][char2_index] = 0;
        }
        return dp[char1_index][char2_index];
    }

요론식으로 하지만 정답은 맞았었지만 시간복잡도 결과가 너무 높았기에 다른 방법을 생각 해보았다.

---

그냥 같은 부분이 있으면 1을 증가시키면서 ans를 업데이트만 해주면 됬었다.

for(int i=1; i< char1.size()+1; i++){
            for(int k=1; k<char2.size()+1; k++){
                if(char1.get(i-1)==char2.get(k-1)){
                    dp[i][k] = 1+dp[i-1][k-1];
                    if(ans<dp[i][k]){
                        ans = dp[i][k];
                    }
                }
            }
        }
        bw.write(ans+"");

Need Know

1. DP

전체 코드 ( Java )

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

class Main{
    static ArrayList<Character> char1 = new ArrayList<>();
    static ArrayList<Character> char2 = new ArrayList<>();
    static int dp[][];
    static int ans = 0;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        set();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }
    static void set() throws IOException {
        String str = br.readLine();
        for(int i=0; i<str.length(); i++){
            char1.add(str.charAt(i));
        }
        str = br.readLine();
        for(int i=0; i<str.length(); i++){
            char2.add(str.charAt(i));
        }
        dp = new int[char1.size()+1][char2.size()+1];
    }
    static void solve() throws IOException {
        for(int i=1; i< char1.size()+1; i++){
            for(int k=1; k<char2.size()+1; k++){
                if(char1.get(i-1)==char2.get(k-1)){
                    dp[i][k] = 1+dp[i-1][k-1];
                    if(ans<dp[i][k]){
                        ans = dp[i][k];
                    }
                }
            }
        }
        bw.write(ans+"");
    }
//    static int recursive(int char1_index,int char2_index ){
//        if(char1_index >= char1.size() || char2_index >= char2.size()){
//            return 0;
//        }
//        if(dp[char1_index][char2_index]!=0){
//            return dp[char1_index][char2_index];
//        }
//        dp[char1_index][char2_index] = 1;
//        if(char1.get(char1_index) == char2.get(char2_index)){
//            dp[char1_index][char2_index] += recursive(char1_index+1,char2_index+1);
//        }else{
//            dp[char1_index][char2_index] = 0;
//        }
//        return dp[char1_index][char2_index];
//    }
}