[백준] 9251/ LCS (골드5)

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

import java.io.*;
import java.util.*;
public class Main
{
    static String a,b;
    static int[][] dp;
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        a = br.readLine();
        b = br.readLine();

        int index = 0;
        int cnt = 0;
        while(true){
            if(index == a.length()) break;

            for(int i=0;i<b.length();i++){
                if(a.charAt(index) == b.charAt(i)){
                    cnt++;
                    index++;
                }
            }
        }

        System.out.println(cnt);
    }
}

그리디 방식으로 풀었지만 아님
그리디는 항상 반례가 있는지 생각해보기. 반례가 있어서 안된다면, dp임
=> dp 방식

import java.io.*;
import java.util.*;
public class Main
{
    static String a,b;
    static int[][] dp;
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        a = br.readLine();
        b = br.readLine();

        int f = a.length();
        int s = b.length();
        dp = new int[f][s];
        dp[0][0] = 0;

        for(int i=0;i<f;i++){
            for(int j=0;j<s;j++){
                if(a.charAt(i) == b.charAt(j)){
                    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[f][s]);
    }
}

=> 인덱스 에러
0부터 시작하면 i-1, j-1가 없기에

import java.io.*;
import java.util.*;
public class Main
{
    static String a,b;
    static int[][] dp;
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        a = br.readLine();
        b = br.readLine();

        int f = a.length();
        int s = b.length();
        dp = new int[f+1][s+1];
        dp[0][0] = 0;

        for(int i=1;i<=f;i++){
            for(int j=1;j<=s;j++){
                if(a.charAt(i-1) == b.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[f][s]);
    }
}