[BOJ] 1958 LCS 3

LCS 3

풀이

• LCS 문제니까 dp 일것이라 생각했고, 문자열이 3개니까 dp 배열이 3차원일 것이라고 예상
• 여차저차 하니까 풀리긴 한 문제...
• LCS 는 "최장 공통 부분문자열" 을 뜻하는 것으로, 중요한 점은 "연속하지 않아도 된다!" 이다.
• 2개짜리 LCS와 다른 점은, 두 문자열이 다른 경우 Math.max() 식이 다른 것 뿐.

  🙆‍♀️ 정답 풀이

  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));
          char[] str1 = br.readLine().toCharArray();
          char[] str2 = br.readLine().toCharArray();
          char[] str3 = br.readLine().toCharArray();
          int[][][] dp = new int[str1.length+1][str2.length+1][str3.length+1];
          for(int i=1;i<=str1.length;i++){
              for(int j=1;j<=str2.length;j++){
                  for(int k=1;k<=str3.length;k++){
                      if(str1[i-1]==str2[j-1] && str2[j-1]==str3[k-1]){
                          dp[i][j][k] = dp[i-1][j-1][k-1]+1;
                      }
                      else{
                          dp[i][j][k] = Math.max(Math.max(dp[i-1][j][k],dp[i][j-1][k]),dp[i][j][k-1]);
                      }
                  }
              }
          }
          System.out.println(dp[str1.length][str2.length][str3.length]);
      }
  }

이제 LCS는 눈감고도 풀겠니?