백준 - LCS3(1958)

오늘 풀어볼 문제는 ⭐LCS3이라는 문제이다.

1. 문제요약

• 총 3개의 문자열이 주어진다.
• 3개의 문자열에서 가장 긴 공통되는 부분의 길이를 찾으면 된다.
• 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.

2. 접근법

1. class 하나 생성
   class Info {
   int now;
   int next;
   int count;
   }

2. 100 * 24의 Info 배열판 생성

3. 그 후 나머지 2가지 입력에 대해 다음 알고리즘 진행
   3.1 for문으로 0~100까지 돌며 현재 문자열과 동일한 게 있나 확인
   3.1.1 동일하면 해당 count ++, 다음 문자열이 같은지 비교. 같으면 해당 문자열로 이동후 3.1.1 재진행
   3.1.2 동일하지 않으면 다시 6.1로 돌아감

4. 가장 큰 count가 정답

2.1 잘못된 이유1 - 잘못된 dp 배열

일단 첫 번째로, 이 문제는 dp긴 하지만 3D DP 문제이다.

2.2 잘못된 이유2 - 알고리즘

일단 기본적으로, 이건 LCS 알고리즘을 알아야 한다.

누워서 보는 알고리즘12

이 분 영상 ㄹㅈㄷ라 쉽게 공부했다.

3. 옳은 접근

1. count [][][] = new int[101][101][101] 을 선언한다.
   우리는 count[1][1][1] 에서부터 최장 길이 기록을 시작할 것이다.

2. 맨 첫 번째 문자가 모두 같다면, count[i][j][k] = count[ i-1 ][j-1][ k-1]에서 +1 이다.

3. 맨 첫 번째 문자가 하나라도 다르다면 count[i][j-1][k-1] , count[i-1][j][k-1], count[i-1][j-1][k], count[i-1][j-1][k-1] 중 가장 큰 값이 count[i][j][k] 의 값이다.

4. 코드

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

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

        String s1 = br.readLine();
        String s2 = br.readLine();
        String s3 = br.readLine();

        int [][][]count = new int[101][101][101];

        // DP 테이블 갱신
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                for (int k = 1; k <= s3.length(); k++) {
                    // 세 문자열의 해당 문자가 모두 일치하는 경우
                    if (s1.charAt(i - 1) == s2.charAt(j - 1) && s2.charAt(j - 1) == s3.charAt(k - 1)) {
                        count[i][j][k] = count[i - 1][j - 1][k - 1] + 1;
                    } else {
                        // 세 가지 방향 중 최댓값을 선택
                        count[i][j][k] = Math.max(Math.max(count[i - 1][j][k], count[i][j - 1][k]), Math.max(count[i][j][k - 1], count[i - 1][j - 1][k - 1]));
                    }
                }
            }
        }

       
        System.out.println(count[s1.length()][s2.length()][s3.length()]);
    }
}