글 읽기 - 재귀를 이용해 풀어봤는데 98%에서 통과를 하지 못합니다.

yoonminsu0617 3년 전 0

자바를 사용 했습니다. LCS의 길이를 구하는 함수입니다.

문제는 반복문을 이용해 해결했지만 재귀를 이용해서 길이를 구하고 싶은데 98%까지는 잘 올라가지만 그 이후

시간 초과가 나버립니다. 무엇이 문제일까요?

import java.io.*;
import java.util.*;
public class Main {
    static int[][] dp = new int[ 1001 ][ 1001 ];
    static char[] str1 = new char[ 1001 ];
    static char[] str2 = new char[ 1001 ];

    public static int recurLCS( int i, int j ) {
        if( i == 0 || j == 0 ) {
            return 0;
        }
        if( dp[ i ][ j ] != 0 ) {
            return dp[ i ][ j ];
        }
        if( str1[ i - 1 ] == str2[ j - 1 ] ) {
            dp[ i ][ j ] = recurLCS( i - 1, j - 1 ) + 1;
        } else {
            dp[ i ][ j ] = Math.max( recurLCS( i - 1, j ), recurLCS( i, j - 1 ) );
        }
        return dp[ i ][ j ];
    }
    
    public static void lcsPrint( int strlen1, int strlen2 ) {
        int i = strlen1;
        int j = strlen2;
        Stack<Integer> st = new Stack<>();

        while( dp[ i ][ j  ] != 0 ) {

            if( dp[ i ][ j ] == dp[ i ] [ j - 1 ] ) {
                j--;
            } else if( dp[ i ][ j ] == dp[ i - 1 ][ j ] ) {
                i--;
            } else if( dp[ i ][ j ] - 1 == dp[ i - 1 ][ j - 1 ] ) {
                st.push( i - 1 );
                i--;
                j--;
            }
        }

        while( !st.isEmpty() ) {
            System.out.print( str1[ st.peek()] );
            st.pop();
        }
    }

    public static void main( String[] args ) throws IOException {
        BufferedReader br = new BufferedReader( new InputStreamReader(System.in));

        str1 = br.readLine().toCharArray();
        str2 = br.readLine().toCharArray();

        int strlen1 = str1.length;
        int strlen2 = str2.length;

        System.out.println( recurLCS( strlen1, strlen2 ));
        lcsPrint( strlen1, strlen2 );

    }
}

minjun13795 3년 전 0

안녕하세요 저도 재귀로 풀다 막혔는데 해결했어요.

저는 lcs를 구할 때 p 배열 사이즈를 +1 하니까 성공했어요. 배열 사이즈를 넘어가 다른 메모리 공간을 참조하여 시간초과가 나버린거죠. (원래는 런타임에러 떠야하지만 이런 경우가 종종 있네요.)

님 코드 같은 경우엔 recurLCS 함수에서 메모리 참조에 대해 확인해보세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <list>
#include <stack>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <string>

using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<pl, pl> pll;
char str1[1001], str2[1001];
ll cache[1000][1000];
pl p[1001][1001];
ll len1, len2;
vector<char> answer;
ll my_func(ll x, ll y, ll idx)
{
	if (x >= len1 || y >= len2) return 0;

	ll& ret = cache[x][y];
	if (ret != -1) return ret;

	if (str1[x] == str2[y]) {
		ret = my_func(x + 1, y + 1, idx+1) + 1;
		p[x][y] = { x+1, y+1 };
	}
	else {
		if (my_func(x, y + 1, idx) > my_func(x + 1, y, idx))
		{
			ret = my_func(x, y + 1, idx);
			p[x][y] = { x, y+1};
		}
		else
		{
			ret = my_func(x + 1, y, idx);
			p[x][y] = { x+1, y };
		}
	}
	return ret;
}
void tracking(ll x, ll y)
{
	if (x == -1 && y == -1)
		return;
	pl next = p[x][y];
	if (str1[x] == str2[y]) answer.push_back(str1[x]);

	tracking(next.first, next.second);
}
int main()
{
	scanf("%s %s", str1, str2);
	len1 = strlen(str1), len2 = strlen(str2);
	memset(p, -1, sizeof(p));
	memset(cache, -1, sizeof(cache));
	ll size = my_func(0, 0, 0);
	printf("%lld\n", size);
	tracking(0, 0);

	for (int i = 0; i < answer.size(); i++) printf("%c", answer[i]);
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

재귀를 이용해 풀어봤는데 98%에서 통과를 하지 못합니다.

yoonminsu0617 3년 전 0

minjun13795 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말