package algo;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BJ_9252 {
static int DP[][];
static String LCS[][];
static char A[];
static char B[];
static String a;
static String b;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
a = br.readLine();
b = br.readLine();
DP = new int[b.length()+1][a.length()+1];
LCS = new String[b.length()+1][a.length()+1];
A = new char[a.length()];
B = new char[b.length()];
for(int i=0; i<a.length(); i++) {
A[i] = a.charAt(i);
}
for(int i=0; i<b.length(); i++) {
B[i] = b.charAt(i);
}
for(int i=0; i<=b.length(); i++) {
for(int j=0; j<=a.length(); j++) {
LCS[i][j] ="";
}
}
// for(int i=0;i<=a.length()+1;i++) {
// Arrays.fill(LCS[i], "");
// }
dpdp();
}
private static void dpdp() {
DP[0][0] =0;
for(int i=1; i<=b.length(); i++) {
DP[i][0] = 0;
}
for(int i=1; i<=a.length(); i++) {
DP[0][i] = 0; // 값 0으로 초기화
}
for(int j=1; j<=b.length(); j++) {
for(int i=1; i<=a.length(); i++) {
if(A[i-1]==B[j-1]) {
DP[j][i] = DP[j-1][i-1] +1;
LCS[j][i] += LCS[j-1][i-1] + A[i-1]; //문자 저장
}else { //a, b 다를 때
DP[j][i] = Math.max(DP[j-1][i], DP[j][i-1]) ;
if(LCS[j-1][i].length() > LCS[j][i-1].length()) {//위에 값이 왼쪽값보다 크면
LCS[j][i] = LCS[j-1][i]; //위에 값 넣어줌
}else {
LCS[j][i] = LCS[j][i-1]; //아니면 왼쪽값 넣어줌
}
}
}
}
// for(int i=0; i<=b.length(); i++) {
// for(int j=0; j<=a.length(); j++) {
//
// System.out.print(DP[j][i]);
// }
// System.out.println();
// }
// for(int i=1; i<=b.length(); i++) {
// for(int j=1; j<=a.length(); j++) {
//
// if(A[i-1]==B[j-1]) {
// DP[j][i] = DP[j-1][i-1] +1;
//
//
// }else {
// DP[j][i] = Math.max(DP[j-1][i], DP[j][i-1]) ;
// }
//
//
// }
//
//
// }
System.out.println(DP[b.length()][a.length()]);
System.out.println(LCS[b.length()][a.length()]);
}
}
여기서 DP[b][a] 이런 식으로 넣어줬는데 값 넣을 때는
b 넣을 자리에 a 넣고 그래서 예제 넣으면 답은 잘 나오는데 백준에서 계속 런타임 에러 떳다.......
꼼꼼히 보자.................................
'백준알고리즘' 카테고리의 다른 글
백준 11403 경로 찾기 JAVA BFS (0) | 2020.06.28 |
---|---|
백준 1927 Java 최소 힙(Heap) (0) | 2020.06.09 |
백준 JAVA 11812 K진 트리 (0) | 2020.05.10 |
백준 1926 그림[BFS] (0) | 2020.04.23 |
백준 11720 숫자의 합 charAt (0) | 2020.04.22 |
댓글