[백준] 9251 LCS - DP JAVA

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

9251번: LCS

코드설명

2차원 DP문제입니다.

 

 

항상 문자열은 2개 주어집니다.

여기서 DP[][] 는 각 부분수열끼리의 최대의 LCS를 의미합니다. 

즉, (0,0)입장에서는 CAPCAK를 기준으로 하였을때 CAPCAK를 다 보는것이 아닌 부분수열 : [ C ] 와 부분수열 : [ A ] 를 비교하여, 각 위치에서의 최대 부분수열의 길이는 얼마일까? 입니다.

즉, [ C ] 부분수열과 [ A ] 부분수열을 비교하였을떄 겹치는게 없으니 0 입니다.

만약, (0, 1) 입장에서는 [C A] 라는 부분수열이 있습니다. 이떄 [C A]와 [ A ]의 LCS는 1입니다.

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

여기서 나온 규칙은 만약 (0, 1) 2열의 값 [ C ],  ( 부분수열으로는 [ A C ] ) 이 같은 문자를 만날때마다 값이 전의 대각선 위치에 해당하는 값에 + 1 을 한 규칙을 찾을 수 있습니다.

(0, 1)를 만날때는 0 ( i == -1 일때는 값이 없음)  + 1

(3, 1)에서 [ CAPC ]를 만날때는 (3 - 1, 1 - 1 ) 의 값인 1 + 1 로 된 것을 볼 수 있습니다. 

점화식으로 표현하면 아래와 같습니다.

dp[r][c] = simulate(r - 1, c - 1) + 1;

만약 같은값이 없다면, 왼쪽 배열의 값과 위의 배열의 값중 최대값으로 갱신합니다.

dp[r][c] = Math.max(simulate(r - 1, c),  simulate(r, c - 1));

 

TOP-DOWN 방식이 아닌 Bottom-UP 방식으로도 가능합니다.

 

 

코드

BOTTOM-UP 방식 ( DP 배열의 SIZE를 +1 시켜서 범위가 나갈시 0으로 처리하여 조건문을 없애줍니다. )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
	public static int N;
	public static char[] str1, str2;
	public static int[][] dp;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	str1 = br.readLine().toCharArray();
    	str2 = br.readLine().toCharArray();
    	
    	dp = new int[str1.length + 1][str2.length + 1];
    	
    	simulate();
    	System.out.println(dp[str1.length][str2.length]);
    }
    
    public static void simulate() {
    	for(int i=1; i <= str1.length; i++) {
    		for(int j=1; j <= str2.length; j++) {
    			if( str1[i-1] == str2[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]);
    			}
    		}
    		
    	}

    }
    
    
}

 

 

BOTTOM-UP 방식 ( 배열의 값을 + 1 시키지 않아서 조건문이 많이들어감 , 음수일경우 처리필요 )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
	public static int N;
	public static char[] str1, str2;
	public static int[][] dp;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	str1 = br.readLine().toCharArray();
    	str2 = br.readLine().toCharArray();
    	
    	dp = new int[str1.length][str2.length];
    	
    	simulate();
    	System.out.println(dp[str1.length - 1][str2.length - 1]);
    }
    
    public static void simulate() {
    	for(int i=0; i < str1.length; i++) {
    		for(int j=0; j < str2.length; j++) {
    			if( str1[i] == str2[j]) {
    				if(i - 1 < 0 || j - 1 < 0) { //하나라도 음수보다 작아진다면 
    					dp[i][j] = 0 + 1;	
    				}
    				else { // 왼쪽 대각선 위의 값에 + 1 을 한 값입니다.
    					dp[i][j] = dp[i-1][j-1] + 1;
    				}
    				
    			}
    			else { //만약 값이 같지않다면, 왼쪽 이나 바로 위쪽 배열의 값중 최대값으로 갱신
    				if( i - 1 < 0 && j - 1 >= 0) {
    					dp[i][j] = dp[i][j-1];
    				}else if( i - 1 >= 0 && j - 1 < 0) {
    					dp[i][j] = dp[i-1][j];
    				}else if( i -1< 0 && j - 1 < 0) {
    					dp[i][j] = 0;
    				}else {
    					dp[i][j] = Math.max(dp[i-1][j],  dp[i][j-1]);
    				}
    				
    			}
    		}
    		
    	}

    }
    
    
}

 

TOP-DOWN

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
	public static int N;
	public static char[] str1, str2;
	public static Integer[][] dp;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	str1 = br.readLine().toCharArray();
    	str2 = br.readLine().toCharArray();
    	
    	dp = new Integer[str1.length][str2.length];
    	
    	answer = simulate(str1.length - 1, str2.length - 1);
    	System.out.println(answer);
    }
    
    public static int simulate(int r, int c) {
    	
    	if(r == -1 || c == -1) {
    		return 0;
    	}
    	
    	if(dp[r][c] == null) {
    		dp[r][c] = 0;
    		
    		if(str1[r] == str2[c]) {
    			dp[r][c] = simulate(r - 1, c - 1) + 1;
    		}
    		else {
    			dp[r][c] = Math.max(simulate(r - 1, c),  simulate(r, c - 1));
    		}
    	}
    	return dp[r][c];
    	
    }
    
    
}