백준 9252번 (java) DP, LCS

---

백준 9252: lcs 2 JAVA

---

관찰

lcs 전형적인 dp문제인데 이것은 dp를 타고 최적해를 구한 경로를 찾아서 출력해야 한다..
DP 테이블을 그려서 규칙을 찾아보자

---

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static int n,m;
    static char[] chr1,chr2;
    static int[][] dp;
    static Stack<Character> stack;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        chr1 = br.readLine().toCharArray();
        chr2 = br.readLine().toCharArray();

        n = chr1.length;
        m = chr2.length;

        dp = new int[n+1][m+1];
        stack = new Stack<>();

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                int max = -1;
                if(chr1[i-1] == chr2[j-1]){
                    if(dp[i-1][j-1] + 1 > max) max = dp[i-1][j-1] + 1;
                }
                if(dp[i-1][j] > max) max = dp[i-1][j];
                if(dp[i][j-1] > max) max = dp[i][j-1];
                dp[i][j] = max;
            }
        }
        int r = n;
        int c = m;
        while(true){
            if(dp[r][c] == 0) break;
            if(dp[r][c] == dp[r-1][c]){
                r--;
            }
            else if(dp[r][c] == dp[r][c-1]){
                c--;
            }
            else{
                stack.push(chr1[r-1]);
                r--;c--;
            }
        }

        sb.append(dp[n][m]).append("\n");
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        System.out.println(sb);

    }

}

---

풀이

DP 테이블을 같은 문자일때 대각선 +1 OR 가로 세로 이렇게 비교해주면서 채워줬다
이렇게 채워주니 다시 찾아갈 때는 같은 문자여서 +1 된 부분이 경로이고 이걸 찾아서 출력해줘야 했다

---

느낀점

최근 경로를 찾아가는 DP를 많이 풀었었는데 이건 또 다른 느낌이라 새로웠다.
DP를 어떻게 채웠는지 명확한 파악을 하고 있는가를 물어보는 문제인 것 같다!