백준 9251 - LCS JAVA

문제/입출력조건/테스트케이스

이 문제는 정말 난감했다.
엄청 간단해 보였는데 결국 구선생님의 도움을 받을 수밖에 없었다.
언제나 조져진 건 나였다...!

 

 

접근과정

1. 그냥 브루트포스로 다 확인하면 되지 않을까?
최대 2의 1000승(부분집합 경우의 수) x 1000(나온 결과와 상대 문자열 비교) 만큼의 무지성 곱이 나와버린다.
2. 맵과 리스트를 이용해서 그래도 dictionary화 해볼까?
->딱히 1번과 큰 차이가 없다
3. 답은 dp였다...
4. dp는 항상 손으로 직접 끄적여보면서 패턴(점화식)을 찾아야 한다는 걸 오늘 깨닫고 어제도 깨닫고... 
5.  구선생님(구글)의 도움으로 어찌저찌 점화식도 구하고 했으나 결국 코딩까지 반이상 복붙하고 말았다.
문제 풇ㅇ

 

 

1. for문 ver

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		char[] a = sc.nextLine().toCharArray();
		char[] b = sc.nextLine().toCharArray();
		int[][] dp = new int[a.length + 1][b.length + 1];

		for (int i = 1; i <= a.length; i++) {
			for (int j = 1; j <= b.length; j++) {
				if (a[i - 1] == b[j - 1]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;

				} else {
					if (dp[i - 1][j] >= dp[i][j - 1]) {
						dp[i][j] = dp[i - 1][j];

					} else {
						dp[i][j] = dp[i][j - 1];
					}
				}
			}
		}
		System.out.println(dp[a.length][b.length]);
	}

}

 

 

2. 재귀함수 버전

import java.util.Scanner;
 
public class Main {
 
	static char[] a;
	static char[] b;
 
	static Integer[][] dp; // 따로 초기화 하지 않고 null 상태로 있으므로 방문 여부를 따로 탐색하지 않아도 됨.
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
 
		// toCharArray() : 문자열을 char[] 배열로 반환해주는 메소드
		a = sc.nextLine().toCharArray();
		b = sc.nextLine().toCharArray();
		
		dp = new Integer[a.length][b.length];
 
		System.out.println(LCS(a.length - 1, b.length - 1));
		
	}
	
	static int LCS(int x, int y) {
		
		// 인덱스 밖 (공집합)일 경우 0 반환
		if(x == -1 || y == -1) {
			return 0;
		}
 
		// 만약 탐색하지 않은 인덱스라면?
		if(dp[x][y] == null) {
			dp[x][y] = 0;
 
			// a의 x번째 문자와 b의 y번째 문자가 같은지 검사
			if(a[x] == b[y]) {
				dp[x][y] = LCS(x - 1, y - 1) + 1;
			}
 
			// 같지 않다면 LCS(dp)[x-1][y]와 LCS(dp)[x,y-1]
			else {
				dp[x][y] = Math.max(LCS(x - 1, y), LCS(x, y - 1));
			}
		}
		
		return dp[x][y];
	}
 
}