[백준(Baekjoon)][자바(java)] 9252 : LCS 2 / 동적 계획법과 최단거리 역추적

 

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

9252번: LCS 2

 

( 9251번 : LCS )

문제  :  https://www.acmicpc.net/problem/9251
풀이  :  https://hyunjiishailey.tistory.com/130

 

문제 풀이

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		char[] s1 = br.readLine().toCharArray(), s2 = br.readLine().toCharArray(); 
		br.close();
		
		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++ ) 
				dp[i][j] = s1[i-1] == s2[j-1] ? 
						dp[i-1][j-1] + 1 : 
						Math.max( dp[i-1][j], dp[i][j-1] );
		
		StringBuilder sb = new StringBuilder();
		i = l1; j = l2;
		while( i >= 1 && j >= 1 ) {
			if( dp[i][j] == dp[i-1][j] )
				i--;
			else if( dp[i][j] == dp[i][j-1] )
				j--;
			else {
				i--; j--;
				sb.insert( 0, s2[j] );
			}
		}
		sb.insert( 0, dp[l1][l2] + "\n" );
		
		System.out.println( sb.toString() );
	}
}

 

-  s1[]와 s2[]의 길이를 각각 구함  ( l1 = s1.length, l2 = s2.length )

-  dp[i][j] ( 0 < i <= l1, 0 < j <= l2 )  =>  i * j 번째 에서 '부분 수열'의 최대 길이

-  dp[i][j] 값은 s1[i-1] == s2[j-1]일 경우 대각선 위쪽의 값( dp[i-1][j-1] ) + 1,
   아닐 경우 그 왼쪽( dp[i][j-1] )이나 위쪽( dp[i-1][j] ) 중 더 큰 값

-  부분 수열의 최대 길이는 dp[l1][l2] 이다

-  i = l1, j = l2 로 초기화 한 후, dp[i][j]를 순회함
  dp[i][j]가 위쪽 값( dp[i-1][j] )과 같으면 한 칸 위로 올라감 ( i-- )
  왼쪽 값( dp[i][j-1] )과 같으면 한 칸 왼쪽으로 옮김 ( j-- )
  둘 다 아닐 경우 대각선 왼쪽 위로 옮기고, ( i--; j-- )
  두 문자열 중 문자가 같아 길이가 늘어난 것이므로 StringBuilder의 제일 앞 offset에 추가 

-  StringBuilder을 한꺼번에 출력

 

					④		③	②	①
			s2	C	A	P	C	A	K
	idx			0	1	2	3	4	5
		dp	0	1	2	3	4	5	6
s1		0	0	0	0	0	0	0	0
A	0	1	0	0	1	1	1	1	1
C	1	2	0	1	1	1	2	2	2
A	2	3	0	1	2	2	2	3	3
Y	3	4	0	1	2	2	2	3	3
K	4	5	0	1	2	2	2	3	4
P	5	6	0	1	2	3	3	3	4