[Softeer] Lv3. 비밀메뉴2 (Java)

1. 문제

• 문제 링크 : Lv3. 비밀메뉴2
• 주제 : LCS, DP

---

2. 풀이 과정 및 정리

이 문제는 두 수열 사이에 공통적으로 포함된 연속된 수열의 최대 길이를 구해야 한다.

여기서 가장 먼저 생각난 것은 LCS 즉, 가장 긴 공통 부분 문자열이다.

 

[LCS 문제 풀이 연습]

https://soo-note.tistory.com/56

[TIL] 동적 프로그래밍 문제 풀이

 

그러나 이 문제에서 LCS로 풀면 틀린다.

왜냐하면 LCS는 공통 부분 수열이므로 연속되지 않아도 되기 때문이다.

 

그래서 나는 LCS를 살짝 변형해서 연속된 공통 부분 수열을 찾아보았다.

기본적인 LCS 알고리즘은 아래와 같다.

for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
        if(a[i] == b[j]) { //같을 경우
            dp[i][j] = dp[i-1][j-1] + 1;
        }
        else { //다를 경우
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
}

만약에 공통된 문자일 경우 1을 더해준다.

아닐 경우 가장 긴 공통 부분 수열을 구해야하므로 앞의 값들 중에서 큰 수를 저장한다.

이 부분을 통해 연속되지 않아도 마지막에 가장 긴 공통 부분 수열을 구하는 것이다.

 

그래서 나는 값이 같은 경우만 생각해서 연속될 수 있도록 했다.

for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
        if(a[i] == b[j]) { //값이 같은 경우
            dp[i][j] = dp[i-1][j-1] + 1;
            result = Math.max(result, dp[i][j]);
        }
    }
}

대신에 가장 긴 길이는 배열의 맨 끝에 저장되지 않고 마지막으로 공통된 문자의 위치에 저장된다.

그러므로 최댓값을 알기 위해 result란 변수를 두어 가장 긴 길이를 찾도록 했다.

---

3. 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] a = new int[n+1];
        int[] b = new int[m+1];

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= m; i++) {
            b[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[n+1][m+1];
        int result = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(a[i] == b[j]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    result = Math.max(result, dp[i][j]);
                }
            }
        }

        bw.write(result + "");
        bw.flush();
        bw.close();
    }
}