99클럽 코테 스터디 34일차 TIL (챌린저): [백준][Java] LCS 3 - 골드5

 

문제 보기

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

 

 

풀이

https://mountain-noroo.tistory.com/30

[백준][C#] 9251 LCS - 골드5

 

예전에 LCS 문제를 푼 적이 있다.

이번엔 그 3차원 배열 버전이다.

 

문제를 푸는 방법은 동일하기 때문에 위 포스팅을 보고 오면 될 것 같다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String str1 = br.readLine();
    String str2 = br.readLine();
    String str3 = br.readLine();

    int[][][] dp = new int[str1.length()+1][str2.length()+1][str3.length()+1];

    for(int i = 0; i <= str1.length(); i++) {
      for(int j = 0; j <= str2.length(); j++) {
        for(int k = 0; k <= str3.length(); k++) {
          if(i == 0 || j == 0 || k == 0) {
            dp[i][j][k] = 0;
            continue;
          }

          if(str1.charAt(i - 1) == str2.charAt(j - 1) && str1.charAt(i - 1) == str3.charAt(k - 1)) {
            dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
          } else {
            dp[i][j][k] = Math.max(dp[i-1][j][k], Math.max(dp[i][j-1][k], dp[i][j][k-1]));
          }
        }
      }
    }

    bw.write(dp[str1.length()][str2.length()][str3.length()] + "");
    bw.flush();
    bw.close();
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/1958.%E2%80%85LCS%E2%80%853

CodingTest_AutoSave/백준/Gold/1958. LCS 3 at main · MetroDefro/CodingTest_AutoSave