글 읽기 - 시간초과 발생 조언부탁드립니다.

iam0woo 5년 전 0

전체단어를 선택경우의수로 작성 하였는데 해결방안좀 부탁드리겠습니다.!

#include <cstdio>
#include <cstring>
#include <cstdlib>

bool chk[26];
int N, K;
char word[50][16];
int max = -1;

void dfs(int index, int select, int size) {
    if(N-index+select <= max) {
        return;
    }
    
    if(index > N-1) {
        if(max<select) {
            max = select;
        }
        if(max == N) {
            printf("%d\n", max);
            exit(0);
        }
        return;
    }
    
    int tmp = size;
    bool chk_tmp[26];
    for(int i=0; i<26; ++i) {
        chk_tmp[i] = chk[i];
    }
    
    for(int i=4; i<strlen(word[index])-4; ++i) {
        if(!chk[word[index][i]-97]) {
            tmp++;
            chk[word[index][i]-97] = true;
        }
    }
    
    if(tmp > K-5) {
        for(int i=0; i<26; ++i) {
            chk[i] = chk_tmp[i];
        }
        if(max < select) max = select;
        dfs(index+1, select, size);
    } else if(tmp == size) {
        dfs(index+1, select+1, tmp);
    } else {
        dfs(index+1, select+1, tmp);
        for(int i=0; i<26; ++i) {
            chk[i] = chk_tmp[i];
        }
        dfs(index+1, select, size);
    }
    
}

int main(int argc, char* argv[]) {
    scanf("%d %d", &N, &K);
    if(K < 5) {
        printf("0\n");
        return 0;
    }
    
    int count = 0;
    if(K == 5) {
        for(int i=0; i<N; ++i) {
            scanf("%s", word[i]);
            for(int j=0; j<strlen(word[i]); ++j) {
                if(chk[word[i][j]-97] == 0) {
                    chk[word[i][j]-97] = 1;
                }
            }
            int cnt = 0;
            for(int j=0; j<26; ++j) {
                if(chk[j]) cnt++;
            }
            if(cnt == 5) {
                count++;
            }
        }
        printf("%d\n", count);
        return 0;
    }
    
    chk['a'-97] = true;
    chk['n'-97] = true;
    chk['t'-97] = true;
    chk['i'-97] = true;
    chk['c'-97] = true;
    
    for(int i=0; i<N; ++i) {
        scanf("%s", word[i]);
    }

    dfs(0, 0, 0);
    
    printf("%d\n", max);
    return 0;
    
}

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

문제

문제

출처

ICPC

시간초과 발생 조언부탁드립니다.

iam0woo 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말