백준 9251번 : LCS

• 분류: 다이나믹 프로그래밍

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s1 = br.readLine();
        String s2 = br.readLine();
        int n = s1.length();
        int m = s2.length();

        int[][] map = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                map[i][0] = 0;
                map[0][j] = 0;
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    map[i][j] = map[i - 1][j - 1] + 1;
                } else {
                    map[i][j] = Integer.max(map[i - 1][j], map[i][j - 1]);
                }
            }
        }

        bw.write(String.valueOf(map[n][m]));
        bw.flush();
    }
}

저는 코틀린이 좋아요 자바 싫어요

import java.lang.Integer.max

fun main() {
    val s1 = readLine()
    val s2 = readLine()

    val n = s1!!.length
    val m = s2!!.length

    val map = Array(n + 1) { Array(m + 1) { 0 } }
    for (i in 1..n) {
        for (j in 1..m) {
            if (s1[i - 1] == s2[j - 1]) map[i][j] = map[i - 1][j - 1] + 1
            else map[i][j] = max(map[i][j - 1], map[i - 1][j])
        }
    }
    println(map[n][m])
}

• 코멘트
  
  동적 프로그래밍의 기초 중의 기초 LCS이다. 뼈에 새기자
  
  동적 프로그래밍의 사고를 그대로 따라간다. 첫 번째 문자열은 i번째까지만, 두 번째 문자열은 j번째까지만 생각했을 때의 LCS를 map[i][j]에 저장해 가는 것이다. 이런 풀이가 가능한 이유는 i<n, j<m이면 map[n][m]를 알아내는 문제 안에 map[i][j]를 알아내는 문제가 그대로 포함되어 있기 때문이다. 이를 optimal substructure 라고 부른다.(쓸모없음)
  아무튼 그 생각을 하며 i는 0부터 s1.length()까지, j는 s2.length()까지 이중 for문을 돈다. 시간 복잡도는 O(mn)이고, s1의 i번째 문자와 s2의 j번째 문자가 일치하면 한 걸음 나아갈 수 있고, 일치하지 않으면 현상 유지를 하면 된다.