글 읽기 - (백트래킹) 시간초과가 발생합니다 ㅠㅠ

rlatjdgus533 3년 전 0

반례 제공 부탁드립니다 ㅠㅠ

#include<iostream>
#include<string>
#include<set>
#include<vector>
#include<stdlib.h>

using namespace std;

bool is_section_string(string S,string A,int start_index)
{
    if(start_index+A.size()>S.size()){
        return false;
    }else{
        for(int i=0;i<A.size();i++){
            if(A[i]!=S[i+start_index]){
                return false;
            }
        }
        return true;
    }
}

void backtracking(string S,vector<string> string_list,int cur_index)
{
    if(cur_index==S.size()){
        printf("%d",1);
        exit(0);
    }

    for(int i=0;i<string_list.size();i++){
        bool case_result=is_section_string(S,string_list[i],cur_index);
        if(case_result==true){
            backtracking(S,string_list,cur_index+string_list[i].size());
        }
    }
}

int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    string S;
    cin>>S;

    int string_list_size;
    cin>>string_list_size;

    vector<string> string_list(string_list_size);
    for(int i=0;i<string_list_size;i++){
        cin>>string_list[i];
    }

    backtracking(S,string_list,0);
    printf("%d",0);
    return 0;
}

pichulia 3년 전 0

시간초과 발생하는 데이터입니다.

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
aa
aaaa
aaaaaa
aaaaaaaaaa
aaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

outersky 3년 전 0

@pichulia

s 길이 100이하인데 저건 120이네요

pichulia 3년 전 1

시간초과 발생하는 데이터 수정본입니다.

참고로 정답은 0입니다.

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
8
aa
aaaa
aaaaaa
aaaaaaaaaa
aaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

sait2000 3년 전 0

무엇보다 일단 백트랙킹으로 푸는 문제가 아닙니다..

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

문제

문제

출처

ICPC

(백트래킹) 시간초과가 발생합니다 ㅠㅠ

rlatjdgus533 3년 전 0

pichulia 3년 전 0

outersky 3년 전 0

pichulia 3년 전 1

sait2000 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말