[백준][C++] 1062 가르침

www.acmicpc.net/problem/1062

1062번: 가르침

 

 

 

알고리즘 종류

완전탐색

 

 

 

사고 과정

읽을 수 있는 최대 단어의 개수를 찾아야 합니다. 시작 글자와 끝 글자를 제외하고 중간에 남는 글자들에서 중복을 제외해야 한다고 생각했습니다. 그리고 a~z중에서 k-5개를 선택해서 남은 글자들을 커버할 수 있는지 확인하면 될 것 같습니다. k가 5미만이면 무조건 0개의 단어를 읽을 수 있습니다.

 

1. 기본으로 선택된 글자들은 미리 선택되게 합니다. 그리고 DFS를 이용한 조합으로  a~z 중에 k-5개를 선택합니다.

 

2. 가공된 입력 단어를 가져옵니다. 그리고 for문으로 돌면서 조합으로 선택된 글자로 커버가 되는지 확인합니다.

 

3. 커버가 되는 단어의 개수를 세어서 최대 개수를 갱신합니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <string>
#include <map>
 
using namespace std;
 
int n, k;
int ans=0;
 
int isSelected[26];
map<char, int> dict;
vector<char> words[51];
vector<char> v;
 
// 선택된 글자로 읽은 수 있는 단어 세기  
void check(){
 
    int cnt = 0;
    for(int i=1; i<=n; i++){ // bring a word
    
        bool flag = true;
        
        for(int j=0; j<words[i].size(); j++){
            char c = words[i][j];                                                                     
            if(!isSelected[c - 'a']) {
                flag = false;
                break;
            }
        }
        
        if(flag) cnt++;
    }
    
    ans = max(cnt, ans);
}
 
// 조합으로 글자 선택  
void dfs(int idx, int cnt){
    
    if(cnt == k-5){
        check();
        return;
    }
    
    for(int i=idx; i<26; i++){
        if(isSelected[i]) continue;
        
        isSelected[i] = 1;
        dfs(i, cnt+1);
        isSelected[i] = 0;
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> k;
    
    if(k < 5) {
        cout << 0 << "\n";
        return 0;
    }
    
    string str;
    
    // 앞 뒤 글자 제거하고, 중복 제거  
    for(int i=1; i<=n; i++){
        cin >>  str;
        
        dict.clear();
        
        for(int j=4; j<str.length()-4; j++){
            char c = str[j];
            if(dict[c]) continue;
            
            words[i].push_back(c);
            dict[c] = 1;
        }
    }
    
    // 기본 글자 표시  
    isSelected['a' - 'a'] = 1;
    isSelected['c' - 'a'] = 1;
    isSelected['i' - 'a'] = 1;
    isSelected['n' - 'a'] = 1;
    isSelected['t' - 'a'] = 1;
    
    dfs(0, 0);
    cout << ans << "\n";
}
 
 

 

 

 

 

시행착오