[BOJ/JAVA] 백준 9251번 : LCS(Longest Common Subsequence)

9251번: LCS

---

 

• 생각

 

fisrtInput이 i까지의 길이, secondInput이 j까지의 길이일 때, dp[i][j]가 있다.

 

1. first[i]와 second[j]가 같다면, dp[i-1][j-1]+1의 값이 dp[i][j]의 값이 될 것이다. 를 토대로 나옴

2. first[i]와 second[j]가 다르다면, first의 마지막 문자 i를 제외한 dp[i-1][j]의 경우의 수가 될 것이다. 마찬가지로 seond의 마지막 문자 j를 제외한 dp[i][j-1]의 경우의 수가 될 것이다. 여기서 우린 최장길이를 선택하는 것이니, 두 개의 경우의 수 중 큰 값을 가지고 온다. 를 토대로 나왔다.

 

https://www.youtube.com/watch?v=EAXDUxVYquY를 참고하였다.

 

• 코드

정답 코드 : LCS 알고리즘의 점화식을 통하여 구현하였다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int[][] dp;
	static int firstInputLength, secondInputLength;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		SetData();
		System.out.println(dp[firstInputLength][secondInputLength]);
	}
	
	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String firstInput = br.readLine();
		String secondInput = br.readLine();

		firstInputLength = firstInput.length();
		secondInputLength = secondInput.length();
		dp = new int[firstInputLength + 1][secondInputLength + 1];
		
		for (int i = 1; i <= firstInputLength; i++) { 
			for (int j = 1; j <= secondInputLength; j++) { 
				if (firstInput.charAt(i - 1) == secondInput.charAt(j - 1)) { 
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else { 
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);				
				}
			}
		}
	}	
}