문제
https://www.acmicpc.net/problem/9252
풀이
점화식을 도출하고 구하는 것은 이전 포스팅 글을 살펴보면 된다.
[Baekjoon] LCS - Java
문제https://www.acmicpc.net/problem/9251 풀이두 문자열이 주어졌을 때, 두 문자열의 공통 부분 수열의 최대 길이를 구하는 문제이다. ACAKCBAK위 두 문자열이 있다고 하자. 그러면 부분 수열은 CAK가 부분
gretea5.tistory.com
최장 공통 부분 수열을 구하는 방법 중에 제일 쉬운 방법은 문자열도 함께 저장해서 문자를 붙이는 형태로 구현하는 것이다.
근데 메모리 초과가 발생한다. 왜일까?
문자를 저장하는데 1byte라고하자.
1 * 1000(문자열의 길이) * 1000 * 1000 = 약 1GB의 메모리가 필요하다.
하지만, 이 문제에서 메모리 제한은 256MB라고 명시되어 있다.
즉, 다른 방법으로 해결해야한다.
배열을 다시 한번 보자.
두 문자열이 "ACAK", "CBAK" 라고 할 때 배열이다.
| C | B | A | K | |
| A | 0 | 0 | 1 | 1 |
| C | 1 | 1 | 1 | 1 |
| A | 1 | 1 | 2 | 2 |
| K | 1 | 1 | 2 | 3 |
두 문자열의 최대 깅리를 가지는 부분 문자열은 CAK이다.
볼드체로 되어 있는 부분에서 문자를 조합한 것이 최대 길이를 가지는 부분 문자열이 된다.
잘 보면, 왼쪽, 위쪽에서 값이 모두 다를 경우에 대한 문자를 조합한 것이다.
그래서 x, y를 우측 하단 값으로 초기화를 하고 값이 위쪽, 왼쪽이 다를 때까지 이동한다. 그리구 그 문자를 저장해서 문자열을 만들면 되는 것이다.
소스코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
char[] arr1 = br.readLine().toCharArray();
char[] arr2 = br.readLine().toCharArray();
int[][] dp = new int[arr1.length + 1][arr2.length + 1];
for (int i = 1; i <= arr1.length; i++) {
for (int j = 1; j <= arr2.length; j++) {
if (arr1[i - 1] == arr2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int x = arr1.length;
int y = arr2.length;
ArrayDeque<Character> stack = new ArrayDeque<>();
while (true) {
if (x == 0 || y == 0) break;
if (dp[x][y] == dp[x - 1][y]) {
x -= 1;
} else if (dp[x][y] == dp[x][y - 1]) {
y -= 1;
} else {
stack.addFirst(arr1[x - 1]);
x -= 1;
y -= 1;
}
}
StringBuilder sb = new StringBuilder();
sb.append(dp[arr1.length][arr2.length]).append("\n");
while (!stack.isEmpty()) {
sb.append(stack.removeFirst());
}
System.out.print(sb);
br.close();
}
}
실행결과

'Problem Solving > Baekjoon' 카테고리의 다른 글
| [Baekjoon] 텀 프로젝트 - Java (0) | 2025.09.10 |
|---|---|
| [Baekjoon] 스티커 - Java (0) | 2025.09.09 |
| [Baekjoon] LCS - Java (0) | 2025.09.06 |
| [Baekjoon] DSLR - Java (0) | 2025.09.04 |
| [Baekjoon] 교환 - Java (0) | 2025.08.31 |