[백준] G5 LCS (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

9251번: LCS

[문제] 

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

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

[입력]

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

[출력]

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

 

---

[풀이]

1. 2개의 문자열을 입력받아준다.

2. dp 배열을 만들어 1번 문자열은 가로, 2번 문자열은 세로로 잡아주고 0으로 초기화해준다.

3. 문자를 비교하면서 같은 문자가 나왔다면 왼쪽 대각선 위의 값 + 1을 dp 배열에 넣어준다.

4. 문자가 다르다면 왼쪽과 위쪽 값을 비교해 더 큰 값을 입력해준다.

5. 마지막에 담긴 값을 결과값으로 출력한다.

[접근]

1. LCS 알고리즘을 사용해서 문제를 해결하면 되겠다고 생각하였다.

2. LCS 알고리즘의 점화식

공통 부분
    dp[i][j] = dp[i - 1][j - 1] + 1;

다른 부분
    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

[코드]

import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 값 입력받기
		String str1 = br.readLine();
		String str2 = br.readLine();
		// dp 배열
		int[][] dp = new int[str1.length() + 1][str2.length() + 1];
		
		// 1번 문자열로 가로 0으로 초기화
		for(int i = 0; i <= str1.length(); i++)
			dp[i][0] = 0;
		// 2번 문자열로 세로 0으로 초기화
		for(int i = 0; i <= str2.length(); i++)
			dp[0][i] = 0;
		
		/*
		비교하는 위치의 문자가 같으면 현재 위치 값 : 왼쪽 대각선 값 + 1
		비교하는 위치의 문자가 같지 않으면 현재 위치 값 : max(왼쪽 값, 위쪽 값)
	    */
		for(int i = 1; i <= str1.length(); i++) {
			for(int j = 1; j <= str2.length(); j++) {
				// 같은 문자가 나왔다면
				if (str1.charAt(i - 1) == str2.charAt(j - 1))
					// 왼쪽 대각선 값 + 1
					dp[i][j] = dp[i - 1][j - 1] + 1;
				else  // 아니라면
					// 왼쪽 값 vs 위쪽 값
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
		
		System.out.println(dp[str1.length()][str2.length()]);
	}
}