[BaekJoon] 9251 LCS (Java)

🔗 문제 링크

https://www.acmicpc.net/problem/9251

📝 문제 풀이 방법

문제는 두 문자열의 겹치는 부분 수열 중에서 가장 길이가 긴 수열의 길이를 찾는 문제이다.

해당 문제 이전 문제와 동일하게 Dynamic Programming으로 해결하는 문제이다.

문제 풀이는 다음 표와 같은 식으로 해결하였다.
1. 2개의 수열의 문자들을 통해 2차원 배열(dp)을 생성한다.
2. 문자열 B에 있는 문자가 문자열 A에 있는지 자리를 하나씩 체크하며 2중 for문을 돌게된다.
3. 만약 같은 문자가 확인된다면 배열에서 해당 그 문자가 나오기 전까지 가장 크기가 큰 수를 찾는다.
4. 3에서 찾은 가장 큰 수+1이 현재 그 문자의 위치에 저장된 값보다 더 크다면 값을 업데이트 해준다.

👨🏻‍💻 작성한 코드

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



public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		char[] strArr1 = br.readLine().toCharArray();
		char[] strArr2 = br.readLine().toCharArray();
		
		int[][] dp = new int[strArr2.length+1][strArr1.length];
		
		for (int i=0; i< strArr1.length; i++) {
			dp[0][i] = 0;
		}
		

		for (int i=0; i<strArr2.length ; i++) {
			int max = 0;
			for (int j=0; j<strArr1.length; j++) {
				dp[i+1][j] = dp[i][j];
				if (strArr2[i] == strArr1[j]) {
					for (int k=0; k< j; k++) {
						if (dp[i][k] > max) max = dp[i][k];
					}
					
					dp[i+1][j] = dp[i+1][j] < max+1 ? max+1: dp[i+1][j];
				}
			}
		}
		
        	// 최종 결과(max값) 도출
		int max = 0;
		for (int j=0; j<strArr1.length; j++) {
			if (dp[strArr2.length][j] > max) max = dp[strArr2.length][j];
		}
		
		System.out.println(max);
	}

}