LCS (백준 9251번) [JAVA]

 

문제

문제 링크 : www.acmicpc.net/problem/9251

9251번: LCS

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	256 MB	19838	8071	6053	41.138%

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

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

입력

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

출력

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

 

풀이

처음에 나름 DP를 이용해 재귀적으로 풀었으나, 시간초과가 떴다.

사실 두개가 뭐가다른지 잘 모르겠다.

JLIS 풀었을 때를 참고해서,

둘이 같을 때 LCD(ai,bi) = 1 + LCD(ai-1,bi-1);

둘이 다를 때 LCD(ai,bi) = Max( LCD(ai-1,bi) , LCD(ai, bi-1) );

이렇게 나누면, LCD(ai,bi)일때 그전에 뭐가되었던 간에 항상 최대값으로 남게 된다.

이제 동적 프로그래밍으로 subset[ai] [bi] 에 답을 계속 저장해 둔 뒤

2중 for문으로 subset을 다 채워주면 된다.

이때 0,0이 입력되었을 때도 LCD를 유지하기 위해 -1이 들어오면 0으로 리턴하게 했다.

우선 시간복잡도는 2중FOR문을 한번씩 순회함으로 (DP로 이전 값들 저장되어 있으므로) $O(N^2)$이다.

 

코드

public class Main {
public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    static int[][] subsets;
    static char[] a;
    static char[] b;
    public static void main(String[] args)throws Exception {
    		a = br.readLine().toCharArray();
    		b = br.readLine().toCharArray();
    		
    		if(a.length ==0 || b.length == 0) {
    			System.out.println(0);
    			return;
    		}
    		
    		subsets = new int[a.length][b.length];
    		
    		for(int i=0; i<a.length; i++) {
    			for(int j=0; j<b.length; j++) {
    				subsets[i][j] = -1;
    			}
    		}
    		
    		for(int ai=0; ai<a.length; ai++) {
    			for(int bi =0; bi<b.length; bi++) {
    				LCS(ai,bi);
    			}
    		}
    		System.out.println(subsets[a.length-1][b.length-1]);
    }

    public static int LCS(int ai, int bi) {
    	
    	if(ai == -1 || bi == -1) return 0;
    	if(subsets[ai][bi] != -1) return subsets[ai][bi];
    	
    	subsets[ai][bi] = 0;

    	if(a[ai] == b[bi]) {
    		subsets[ai][bi] = 1 + LCS(ai-1,bi-1);
    	}
    	else {
    		subsets[ai][bi] = Math.max(LCS(ai-1,bi), LCS(ai,bi-1));
    	}
    	return subsets[ai][bi];	
    }
}

 

코드2 (재귀)

public static void getMax(int ai, int bi, int temp) {
    	if(ai >= a.length || bi >= b.length) {
    		ans = Math.max(ans, temp);
    		return;
    	}
    	//탈출조건
    	if(subsets[ai][bi] > temp) return;	
    	
    	if(a[ai].equals(b[bi])) {
    		temp++;
    		subsets[ai][bi] = temp;
    		getMax(ai+1, bi+1, temp);
    	}
    	else {
    		subsets[ai][bi] = temp;
    		getMax(ai, bi+1, temp);
    		getMax(ai+1, bi, temp);
    	}
    }
}

 

결과