[C++/Java] 백준 9251번 LCS

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

풀이

DP를 이용해서 푸는 문제이다.

입력받는 두 문자열을 a, b 라고 하자.
dp[i][j] 를 a의 앞 i번째까지, b의 앞 j번째까지 봤을 때 LCS 길이라고 정의한다.

• a의 i번째 문자와 b의 j번째 문자가 같을 때
  dp[i][j] = dp[i-1][j-1] + 1

• a의 i번째 문자와 b의 j번째 문자가 다를 때
  이 경우는 a의 i번째 문자를 제외하거나, b의 j번째 문자를 제외했을 때 더 긴 LCS를 선택한다.
  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

코드

cpp

#include <bits/stdc++.h>

using namespace std;

int main() {
    string a, b;
    cin >> a >> b;

    int n = a.size();
    int m = b.size();

    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(a[i-1] == b[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    cout << dp[n][m]; 
}

java

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String[] args) throws Exception{
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String a = br.readLine();
	    String b = br.readLine();
	    
	    int n = a.length();
	    int m = b.length();
	    
	    int[][] dp = new int[n+1][m+1];
	    
	    for(int i=1; i<=n; i++) {
	        for(int j=1; j<=m; 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[n][m]);
	}
}