백준 9251번: LCS

문제

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

9251번: LCS

---

풀이

문자로 된 두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것의 길이를 구하는 문제입니다. 

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK로 길이는 4입니다.

---

코드

자바

탑다운 방식을 이용한 코드입니다.

dp 배열은 임의의 수 x, y가 있을 때 str1.charAt(0부터 x까지)와 str2.charAt(0부터 y까지)가 조건에 맞춰 가질 수 있는 가장 긴 부분 수열의 길이를 의미합니다.

LCS 함수에서 dp[x][y]가 null이라면 str1.charAt(x)와 str2.charAt(y)를 비교합니다. 만약 같다면 LIS(x - 1, y - 1)을 통해 dp[x - 1][y - 1]을 받아 1을 더해준 값을 dp[x][y] 값에 넣어주고 다르다면 LCS(x - 1, y)와 LCS(x, y - 1)을 통해 dp[x - 1][y]와 dp[x][y - 1] 중 큰 값을 넣어준 뒤에 그 값을 반환합니다.

모든 입력이 끝나면 x가 str1.length() - 1이고 y가 str2.length() - 1, 즉 각 문자열의 끝부분이라고 할 때 LCS(x, y)을 실행하여 str1.charAt(0부터 x까지)와 str2.charAt(0부터 y까지)가 조건에 맞춰 가질 수 있는 가장 긴 부분 수열의 길이를 구하여 출력합니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    static String str1, str2;
    static Integer[][] dp;

    static int LCS(int x, int y) {
        if (x == -1 || y == -1) return 0;
        if (dp[x][y] == null) {
            if (str1.charAt(x) == str2.charAt(y)) {
                dp[x][y] = LCS(x - 1, y - 1) + 1;
            } else {
                dp[x][y] = Math.max(LCS(x - 1, y), LCS(x, y - 1));
            }
        }
        return dp[x][y];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str1 = br.readLine();
        str2 = br.readLine();
        dp = new Integer[str1.length()][str2.length()];
        System.out.println(LCS(str1.length() - 1, str2.length() - 1));
    }
}

C언어

바텀업 방식을 이용한 코드입니다.

dp 배열은 탑다운 방식의 코드에서의 의미와 동일하지만 임의의 수 x, y가 있을 때 str1[0부터 x까지]와 str2[0부터 y까지]가 조건에 맞춰 가질 수 있는 가장 긴 부분 수열의 길이를 dp[x + 1][y + 1]에 저장합니다.

이후 i와 j를 포함한 이중 for문을 실행하여 str1[i - 1]과 str2[j - 1]이 같다면 dp[i - 1][i - 1]에 1을 더해준 값을, 다르다면 dp[i - 1][j]와 dp[i][j - 1] 중 큰 값을 dp[x][y] 값에 넣어줍니다.

모든 입력이 끝나면 x가 strlen(str1)이고 y가 strlen(str2), 즉 각 문자열의 끝부분 + 1이라고 할 때 dp[x][y]을 출력하여 str1[0부터 x - 1까지]와 str2[0부터 y - 1까지]가 조건에 맞춰 가질 수 있는 가장 긴 부분 수열의 길이를 구하여 출력합니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define math_max(a, b) a > b ? a : b
main() {
	char str1[1001], str2[1001];
	scanf("%s %s", str1, str2);
	int x = strlen(str1), y = strlen(str2);
	int** dp = (int**)malloc(sizeof(int*) * (x + 1));
	for (int i = 0; i <= x; i++) {
		dp[i] = (int*)malloc(sizeof(int) * (y + 1));
		for (int j = 0; j <= y; j++) {
			dp[i][j] = 0;
		}
	}
	for(int i = 1; i <= x; i++) {
		for (int j = 1; j <= y; j++) {
			if (str1[i - 1] == str2[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]);
			}
		}
	}
	printf("%d", dp[x][y]);
}

 

---

결론

자바로 탑다운 방식을 이용한 코드에서 dp 배열을 Integer가 아니라 int로 잡으면 LCS 함수 안의 조건문을 null이 아니라 0으로 잡으면 dp[x][y]가 0인 경우가 너무 많기 때문에 시간 초과가 발생했는데 이를 해결하기 위해서 함수를 실행하기 전에 dp 배열의 모든 값을 -1 같은 값으로 초기화해줄 수 있었지만 의미가 없다고 판단하여 그러지 않았습니다.