[백준] 1062번: 가르침 | C++

https://www.acmicpc.net/problem/1062

1062번: 가르침

 

틀린 이유

1. K=5 일 때, antatica 처리를 하지 않았다.

2. 연산자 우선순위를 고려하지 못했다.

- 코드 주석 (1)에서 learned_bit & w 는 AND 연산한 bit를 반환한다. 그런데 if의 조건문은 0이 아닌 것은 모두 참으로 판별하므로 하나 이상 일치하는 bit가 있을 경우 모두 cnt++ 연산 되었다.

조건문을 learned_bit & w==w 라고 코드를 고쳐보기도 했는데 결과가 똑같길래... 뭐지? 어디서 틀린거지...? 한 시간을 고민했다... 

 

정답은... 연산자 우선순위..... 설마 했는데... ==이 당연히 마지막인지 알았지..

비트 연산자가 후순위구나......................

 

정답코드

그지 같은 것... 드디어 풀었다.

#include<iostream>
#include<vector>
#include<algorithm>
#define fse(A,B,C) for(int i=A;i<B;i+=C) 
using namespace std;
int N,K;
vector<int> word;
int answer;
void dfs(int start,int learned_bit,int depth){
    if(depth==0){
        int cnt=0;
        for(auto w:word){
            if(w==(learned_bit & w)) cnt++;  // ...(1)
        }
        answer=max(answer,cnt);
        return;
    }else{
        for(int i=start+1;i<26;i++){ //b부터 시작
            if(learned_bit&(1<<i)) continue;
            dfs(i, learned_bit|(1<<i) ,depth-1);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>N>>K;

    int learned_bit=0;
    char must[]={'a','n','t','i','c'};
    for(auto m:must) learned_bit|=1<<(m-'a');

    fse(0,N,1) {
        string tmp;
        cin>>tmp;
        string subbed=tmp.substr(4,tmp.size()-8);
        int bitmask=0;
        for(auto s:subbed){
            bitmask|=1<<(s-'a');
        }
        if(subbed.length()==0) bitmask=1;
        word.push_back(bitmask);
    }

    if(K>=26) answer=N;
    else if (K>=5) dfs(0,learned_bit,K-5);

    cout<<answer;
}