Solution

Memo

  • 공통부분수열, 기억이 안나고 푸는 특정한 방법이 있다는게 기억나서 풀이를 찾아서 구현했다.
  • 천천히 생각했으면 풀었거나 기억이 났을 것 같은데, 직전에 풀었던 공통수열로 생각하다가 점화식에 집착하다 목풀었다.
// Baekjoon - 9251
// https://www.acmicpc.net/problem/9251

use std::io::{self, Read, Write};

fn main() {
    let mut stdin = io::stdin().lock();
    let mut stdout = io::stdout().lock();
    let mut input = String::new();
    stdin.read_to_string(&mut input).unwrap();
    let mut lines = input.lines();

    let first_str: Vec<char> = lines.next().unwrap().chars().collect();
    let second_str: Vec<char> = lines.next().unwrap().chars().collect();

    let m = first_str.len();
    let n = second_str.len();

    let mut dp = vec![vec![0; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            if first_str[i - 1] == second_str[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }

    write!(stdout, "{}", dp[m][n]).unwrap();
}