[백준(Baekjoon)][자바(java)] 9251 : LCS / 동적 계획법 1

 

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

9251번: LCS

 

< 풀이 방법 >

▶  두 문자열 s1, s2를 각각 한 글자씩 비교하며 LCS를 저장할 2차원 dp배열 생성

 --  (l1+1)*(l2+1)   ( l1 : s1의 길이, l2 : s2의 길이 )

▶  s1_i 와 s2_j 가 같으면, LCS는 s1_i-1 와 s2_j-1까지의 LCS보다 하나 늘어남 

 ☞  dp[i-1][j-1] + 1

▶  s1_i 와 s2_j 가 같지 않으면, LCS는 s1_i-1 와 s2_j까지의 LCS, s1_i 와 s2_j-1까지의 LCS 중 더 큰 값이 됨

 ☞  Max( dp[i-1][j], dp[i][j-1] )

 

알고리즘 참고 : 「쉽게 배우는 알고리즘」 (한빛아카데미)

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		String s1 = sc.nextLine(), s2 = sc.nextLine();
		int l1 = s1.length(), l2 = s2.length(), i, j;
		int dp[][] = new int[l1+1][l2+1];
		
		for( i = 1; i <= l1; i++ ) {
			for( j = 1; j <= l2; j++ ) {
				if( s1.charAt(i-1) == s2.charAt(j-1) )
					dp[i][j] = dp[i-1][j-1] + 1;
				else
					dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1] );
			}
		}
		
		System.out.println( dp[l1][l2] );
		sc.close();
	}

}