글 읽기 - 14408번 어떻게 시간을 줄여야 될까요.. ㅠㅠ

hanorang2 5년 전 0

각각의 문자열에 대해서 점괘판의 좌우, 위아래 string과 비교해서 그 중 가장 큰 값을 출력하도록 하였습니다!

비교하는 과정에서는 동적계획법을 사용해서 공통 부분 문자열을 구했는데요, 자꾸 시간초과가 뜨네요 ㅠㅠ

어디를 놓치고 있는 걸까요? 아니면 더 좋은 방법이 있을까요?

#include <iostream>
#include <algorithm>
using namespace std;

int n,m;
char pan[101][101];
int dp[31][101];

int compare(string s1, string s2){
    int result = 0;
    for(int i=1;i<=s1.length();i++){
        for(int j=1;j<=s2.length();j++){
            if(s1[i-1]==s2[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
                if(result < dp[i][j]) result = dp[i][j];
            }
            else{
                dp[i][j] = 0;
            }
        }
    }
    return result;
}

int check(string str){
    int max = 0;
    //left, right
    for(int i=0; i<m; i++){
        int left, right;
        string s;
        for(int j=0; j<n; j++){
            s += pan[i][j];
        }
        left = compare(str, s);
        reverse(s.begin(), s.end());
        right = compare(str, s);
        if(left > right){
            if(left > max) max = left;
        }else{
            if(right > max) max = right;
        }
    }
    //up, down
    for(int i=0; i<n; i++){
        int up, down;
        string s;
        for(int j=0; j<m; j++){
            s+= pan[j][i];
        }
        up = compare(str, s);
        reverse(s.begin(), s.end());
        down = compare(str, s);
        if(up > down){
            if(up > max) max = up;
        }else{
            if(down > max) max = down;
        }
    }
    return max;
}

int main(int argc, const char * argv[]) {
    cin >> n >> m;
    for(int i=0; i<n; i++){
        scanf("%s", pan[i]);
    }
    int p, k; scanf("%d%d",&p,&k);
    for(int i=0; i<p; i++){
        string s; cin >> s;
        printf("%d\n", check(s));
    }
    return 0;
}

kdk8361 5년 전 1

check 함수를 부르는 횟수가 O(p)고 compare함수 가 O(4n)번 사용될거고

compare함수 자체 시간복잡도가 O(nk)기 때문에 O(4kpn^2)이 걸리겠네요.

그리고 string s를 만들기 위해서 걸리는 시간만 check함수 한번당 O(4n^2)기 때문에

O(4pn^2)이 추가로 소모되겠죠.

거기에 제가 알기로 string을 함수의 인자로 넘기게 되면 깊은 복사가 일어난다고 알고있습니다.

O(kp+4p(n+k))가 추가로 필요하겠네요.

알고리즘은 트라이(trie)를 한번 보시는걸 추천합니다.

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

문제

문제

출처

ICPC

14408번 어떻게 시간을 줄여야 될까요.. ㅠㅠ

hanorang2 5년 전 0

kdk8361 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말