글 읽기 - 시간초과의 원인

rlathdwls2 4년 전 0

안녕하세요?

질문 읽어주셔서 감사합니다.

문제풀이를 하던 중 시간초과가 계속 발생하였습니다.

추정하고 있는 원인은

알파벳 조합이 만들어 졌을때

모든 단어를 탐색하며

각 단어당 안배운 단어가 있는지 확인 하고 있는 것입니다.

Worst Case로

(50개의 단어 * 26개의 알파벳) ^ 21(조합)

이 발생하여 시간초과가 날 수 밖에 없는 코드입니다.

하지만 아직 부족한 실력 탓인지

이를 개선할 방법을 혼자서 찾지 못하고 있습니다.

어떻게 하면 백트랙킹을 활용하여 시간초과를 해결할 수 있을지

알려주신다면 정말 감사하겠습니다.

도움 감사드립니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>


#define MAX_N 51
#define MAX_K 27
#define EMPTY ""
using namespace std;
vector<string> inputs;
bool contains[MAX_K];
char alphabets[MAX_K];
bool selected[MAX_K];
int n,k;
int ret;

bool learned(string s){
    for(int idx = 0 ; idx < s.size() ; idx++){
        char ch = s[idx];
        if(!selected[ch-'a'])
            return false;
    }
    return true;
}

int completeNum(){
    int cnt = 0;
    for(int i = 0 ; i <  inputs.size() ; i++){
        if(learned(inputs[i])){
            cnt++;
        }
    }
    
    return cnt;
}

void dfs(int here, int cnt){
    if(cnt == k){
        int learnCnt = completeNum();
        ret = max(ret, learnCnt);
        return;
    }
    
    for(int there = here ; there < MAX_K ; there++){
        if(!selected[there] && contains[there]){
            selected[there] = true;
            dfs(there, cnt+1);
            selected[there] = false;
        }
    }
}

string filter(string s){
    return s.substr(4, (s.size()-8));
}

void build(){
    ret = 0;
    inputs = vector<string>(n);
    string s;
    for(int idx = 0 ; idx < MAX_K ; idx++){
        alphabets[idx] = 'a'+idx;
    }
    
    for(int i = 0 ; i < n ; i++){
        cin>>s;
        s = filter(s);
        
        for(char c : s){
            contains[c-'a'] = 1;
        }
        inputs[i] = s;
    }
}

int main(int argc, const char * argv[]) {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin>>n>>k;
    build();
    dfs(0, 0);
    cout<<ret<<endl;
    return 0;
}

rlathdwls2 4년 전 0

자답 합니다.

사전에 a, c, i, n, t

알파벳을 선택되었다고 표시를 한 후 조합을 생성하니

시간 초과가 해결 되었습니다.

void preLearn(){
    char pre[5] {'a','c', 'i', 'n', 't'};
    for(int i = 0 ; i < 5 ; i++){
        char ch = pre[i];
        selected[ch-'a'] = true;
        k-=1;
    }
}

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

문제

문제

출처

ICPC

시간초과의 원인

rlathdwls2 4년 전 0

rlathdwls2 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말