[Java]백준 BaekJoon.AC 9251 : LCS(다이나믹 프로그래밍 사용)

 

 

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

9251번: LCS

 

 

새로운 도전의 연속인 코딩 연습에서, 새로운 도전에 시간이 많이 걸리는 내겐 참 어렵다...

 

LCS를 이해하는 데에도 많은 시간이 걸렸다.

어려워서가 아니라 배움이 귀찮아서...ㅠ

얼른 습관을 다시 찾아야겠다...!!

 

LCS는 부분집합?(공부를 안하니 이제 용어도 가물가물하다..) 같은 느낌으로 적절히 연산해주는 문제였다.

가령 {A, B}와 {B}를 곱하면 {AB, BB}가 되는 느낌으로다가.. 하나하나 비교해주면 된다.

 

그렇지만 스펠링마다 일일이 비교하기엔 막대한 시간이 소요된다.

이럴 땐 다이나믹 프로그래밍이 유익하다.

이전 결과에 살을 붙여주는 격으로 점점 그 크기를 키워가는 것.

 

스펠링을 하나씩 늘려가며 Top-Down으로 내려갔다.

덕분에 배열 검사를 뒤집어 해야 했지만 난 어렵고 복잡해도 편한게 좋다^^

큰 틀을 이해한다면 코드구현은 어렵지 않았다.

크게 어렵지 않은 코드들을 사용해 완성할 수 있었다.

 

핵심은 서로의 마지막 스펠링끼리 비교해주고,

그 스펠링이 같다면 구하려는 값의 배열 왼윗쪽 대각선에 있는 값에 1 더한 값을 부여하는 것.

만약 다르다면 구하려는 값의 배열 윗값과 왼값을 비교해 큰 값을 부여하는 것.

 

이를 위해 단어길이보다 한 칸 더 크게 배열을 책정했다.

 

 

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

public class Main {
	
	static char[] one;
	static char[] two;
	static int[][] match;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
		one = br.readLine().toCharArray();
		two = br.readLine().toCharArray();
    	
		match = new int[one.length+1][two.length+1];
		
		mix();
		
		System.out.print(match[one.length][two.length]);
	}
	
	public static void mix() {
		
		for(int i=0; i<two.length; i++) {
			for(int j=0; j<one.length; j++) {
				if(two[i]==one[j]) {
					match[j+1][i+1] = match[j][i] + 1;
				}else {
					match[j+1][i+1] = Math.max(match[j][i+1], match[j+1][i]);
				}
			}
		}
		
	}
}