[Softeer] [21년 재직자 대회 본선] 비밀메뉴2 / ProblemId 633 [JAVA]

문제 링크 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=633 

Softeer

 

재직자 본선 문제 1번

A수열과 B 수열의 가장 긴 '연속된' 공통 부분 수열의 길이를 찾는 문제이다

 

방법

 

1. 길이를 1~3000까지 시도해보는 것이다.

 -> 3000(N) * 3000(M) * 2999 * 3000 / 2 (1~3000까지의 합) 

 -> 1~3000까지 시도해볼 필요가 없다 (1500을 시도했을 때 실패했다면 0~1499중에 정답이 있다)

 -> 이분탐색으로 3000(N) * 3000(M) * 12이 가능하다.

 -> 그래도 시간 내에 해결하기 불가능해 보인다.

 

2. 연속된 공통 부분 수열의 길이는 두 배열의 원소의 값이 같다면,

두 배열의 이전까지 연속된 공통 수열의 길이 + 1 임을 이용한다.

 -> 이를 이용하려면 A배열과 B배열의 원소의 값이 같을 때, 이전 원소까지의 연속된 공통 수열의 길이가 저장돼 있음이 보장돼야 한다.

 -> A배열의 i번째 원소까지의 연속된 부분수열과 B배열의 j번째 원소까지의 가장 긴 연속된 부분수열의  공통 부분 수열의 길이를 배열[i][j]에 저장하는 것을 반복한다

 

 

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

public class Main {
    public static int N,M,K;
    public static int A[],B[];
    public static int dp[][];

    public static int dfs(int i,int j){
        if(i<0 || j <0) return 0;
        if(dp[i][j]!=0) return dp[i][j];
        if(A[i] == B[j]){
            return dp[i][j] = 1 + dfs(i-1,j-1);
        }
        return dp[i][j];
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        A = new int[N];
        B = new int[M];
        dp = new int[N][M];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            A[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<M;i++){
            B[i] = Integer.parseInt(st.nextToken());
        }
        int ans = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                ans = Math.max(dfs(i,j),ans);
            }
        }
        System.out.println(ans);
    }
}