[백준] 9251 LCS - 자바

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

9251번: LCS

문제 풀이

유명한 LCS문제다. 작년에 배웠던 알고리즘인데 막상 풀려니 아무 것도 기억이 안 나고 접근법도 모르겠어서 구글링했다. https://st-lab.tistory.com/139로 들어가면 그림으로 자세히 나와있다.

보고 따라치지 말고 한번 보고 분석하고 이해한다음 직접 쳐보는 걸 추천한다.

 

자세한 설명은 위 링크에 써있고 여기선 내가 이해하기 어려웠던 부분을 짚고 넘어갈 생각이다.

https://st-lab.tistory.com/139

X_i == Y_j가 같으면 왜 X_i-1, Y_j-1에서 +1일까? 위나 왼쪽에서 아무거나 가져와서 +1을 해주면 안되는 걸까? 라고 생각했다.

역시 궁금하면 직접 예시를 넣어보면 좋다. ~를 판별하기 때문에 같은 값일 때 논리적 오류가 날 것이라고 생각해서 다음과 같이 수정해봤다.

먼저 (1,2)는 왼쪽 문자열의A와 위족 문자열 A를 포함했기 때문에 이미 증가함을 확인할 수 있다. 이제 다시 한 쪽에서 A가 나오더라도 당연히 이 A는 LCS에 포함되는 문자가 아닐 것이다. 하지만 위에서 언급했던 '위나 왼쪽에서 아무거나 가져와서 +1을 해주면 안되는 걸까?'를 적용시키면 2가 아니라 3이 되어 해당 A를 포함시키게 된다.

이러한 예외를 처리해주기 위해 대각선 방향으로 잡은 듯하다.

코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class b9251 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        int len1 = str1.length();
        int len2 = str2.length();

        // 좌-len2, 상-len1  / [0][], [][0]은 공집합
        int[][] dp = new int[len2 + 1][len1 + 1];

        for (int i = 1; i <= len2; i++) {
            for (int j = 1; j <= len1; j++) {
                if (str1.charAt(j-1) == str2.charAt(i-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[len2][len1]);
    }
}

느낀점

배웠던 내용이라 이해하는 데에는 크게 어렵지 않았지만 구글링을 통해 참고하지 않았다면 못 풀었을 것 같다.