글 읽기 - 시간초과....

kioio5 7년 전 0

1. dfs로 모든 팰린드롬의 경우수를 다찾고 dp테이블에 저장하고

2. 분할하는 모든 경우를 dfs로 찾아서 최소값이 되는 것을 출력하도록 했습니다.

1번과정에서 시간이 오버되는것일까요 2번에서 오버되는것일까요 둘다 접근이 잘못됐을까요..?

#include <cstdio>
#include <iostream>
#include <string.h>
#define MAX_SIZE 2510

using namespace std;

//반례 BBCDDECAECBDABADDCEBACCCBDCAABDBADD 정답 22
// 나는 23 이유는 뒷부분의 A, ABDBA라고 처리가 되어야하는데
// AA BDB로 처리가 됨

//AABDBA

string data;
int len;
int dp[MAX_SIZE][MAX_SIZE];

int dfs(int left, int right)
{
    if(dp[left][right] != -1) return dp[left][right];
    if(left >= right) return dp[left][right] = 1;
    if(data[left] == data[right]) return dp[left][right] = dfs(left + 1, right - 1);
    else return dp[left][right] = 0;
}

int min_dfs(int idx, int d) // d는 1부터
{
    int ret = 0x7fffffff;

    if(idx == len) return d - 1;

    for(int i = len - 1; i >= idx; i--)
    {
        if(dp[idx][i] == 1)
        {
            int tmp = min_dfs(i + 1, d + 1);
            ret = min(ret, tmp);
        }
    }

    return ret;
}

int main()
{
    memset(dp, -1, sizeof(dp));

    cin>>data;
    len = data.length();

    for(int i = 0; i < len; i++)
        for(int j = i ; j < len; j++) dfs(i, j);

    printf("%d", min_dfs(0, 1));

    return 0;
}

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

문제

문제

출처

ICPC

시간초과....

kioio5 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말