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

✏️ 문제 링크

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

1062번: 가르침

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

아니...하... 조합으로 풀어야 겠다는 아이디어를 잘 떠올렸지 나는..!

근데! 근데 시간초가왜나냐고옥!!!!!!!!!해서 prof.google 찾아보니.. 밑에와 같이 풀더라...

난 원래 모르는 단어들을 따로 넣어주고 조합 만들 때 그 단어들만 돌았는데.... 그냥 안배운 모든 단어들을 확인하면서 for문을 돌더랍... 속상

괜챃아 그래도 거의 접근했으니까 앞으로는 디테일한 부분들을 신경씀녀 되줴 💪🏻

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;

vector<string> words;
vector<bool> learned(27, false);
string not_learned="";
int N, K, answer=0;

void func(int k, int idx){
    if(k==K-5){
        int cnt=0;
        for(int i=0; i<words.size();i++){
            int c=0;
            for(int j=0; j<words[i].length();j++){
                if(!learned[words[i][j]-'a']){c++;break;}//there is word that i don't know
            }
            if(c==0) cnt++;
        }
        answer= max(cnt, answer);
    }else{
        for(int i=idx; i<27;i++){
            if(learned[i]) continue;
            learned[i]=true;
            func(k+1, i+1);
            learned[i]=false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin>>N>>K;
    if(K-5<0) {cout<<0<<"\n"; return 0;}
    
    learned['a'-'a']=true;
    learned['n'-'a']=true;
    learned['t'-'a']=true;
    learned['i'-'a']=true;
    learned['c'-'a']=true;
    
    while(N--){
        string word; cin>>word;
        int c=word.length()-8;
        word = word.substr(4, c);
        
        string s="";
        for(int j=0; j<word.size();j++){
            if(!learned[word[j]-'a']) {s+=word[j];}
        }
        
        //배우지 않은 것들 기준으로 
        words.push_back(s);
    }
    
    func(0,0);//k and idx
    
    cout<<answer<<"\n";

    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐