글 읽기 - 1062번 질문 있습니다.

Glitterlance 5년 전 0

이 문제를 풀 때 애초에 a,n,t,i,c를 가르치지 않으면 아무것도 읽을 수 없기 때문에

k가 5 미만이면은 무조건 0을 출력하고,

그 이상일 경우 비트마스크를 이용하여 가르친 알파벳 집합을 만들어서 입력받은 단어의 비트마스크와 AND 연산을 해서 단어를 아는지 확인하려 했습니다.

제가 디버깅을 하면서 내린 결론은, Line 22 ~ Line 29 쪽의 가르친 알파벳 집합을 만들 때, 모든 경우의 수를 따지지 못해서 틀린 것 같은데,

그 이후부터는 아무리 생각해도 어떻게 진행해야 할 지 모르겠습니다.

어떤 부분이 잘못됐는 지 도와주세요..

#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
using namespace std;

int res = -1;

void make_alpha_set(int n,int k,int cur_k,int start,vector<int> &word_mask,int cur_mask){
    if(cur_k == k){
        int cur_res = 0;
        for(int i=0;i<n;i++){
            if((word_mask[i] & cur_mask) == word_mask[i]){
                cur_res += 1;
            }
        }
        if(res == -1 || res < cur_res){
            res = cur_res;
        }
        return;
    }
    for(int i=start;i<26;i++){
        if(i=='a'-'a' || i=='n'-'a' || i=='t'-'a' || i=='i'-'a' || i=='c'-'a'){
            continue;
        }
        cur_mask |= (1<<i);
        make_alpha_set(n,k,cur_k+1,i+1,word_mask,cur_mask);
        cur_mask = cur_mask & (~(1<<i));
    }
}

int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    vector<int> word_mask(n);
    for(int i=0;i<n;i++){
        char cur_word[16];
        scanf("%s",cur_word);
        int len = strlen(cur_word);
        for(int j=0;j<len;j++){
            word_mask[i] |= (1<<(cur_word[j]-'a'));
        }
    }
    int cur_mask = 0;
    cur_mask |= (1<<('a'-'a')); cur_mask |= (1<<('n'-'a'));
    cur_mask |= (1<<('t'-'a')); cur_mask |= (1<<('i'-'a'));
    cur_mask |= (1<<('c'-'a'));
    if(k < 5){
        res = 0;
    }
    else if(k == 26){
        res == n;
    }
    else{
        make_alpha_set(n,k,5,1,word_mask,cur_mask);
    }
    printf("%d\n",res);

    return 0;
}

Glitterlance 5년 전 0

아...그거 고치니까 맞네요...

이런 실수 주의해야겠습니다 ㅠㅠㅠㅠ

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

문제

문제

출처

ICPC

1062번 질문 있습니다.

Glitterlance 5년 전 0

Glitterlance 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말