[ 백준 BOJ ] 1062번 - 가르침 (C++)

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

 

생각 흐름

1. 그리디적으로 map으로 문자의 개수를 세서 가장 많은 것을 순서로 단어를 골라준다.
   • 가장 많은 것으로 K개 골랐는데, 하나도 안 만들어지는 경우가 존재하므로 폐기
   • 예를 들어 한 단어에 같은 문자가 여러 개일 경우
2. 단어에 대해 dfs를 돌면서 문자를 map에 저장하는 방식 생각
   • 기본적으로 시간 복잡도가 2^N이므로 시간초과가 날 거 같다고 생각하여 폐기
3. 알파벳 문자에 대해 K개 만큼 조합을 구해서 비교하기로 결정
   • N이 50이고 모든 단어가 15자리로 최악의 상황을 가정
   • 기본적으로 anta, tica에 대해 antic로 5개를 미리 없앨 수 있으므로 조합의 최대 개수는 21C10으로 35만 정도이다.
   • 조합이 완성된 후 15자리에서 8자리를 뺀 7자리에 대해서만 검증하면 된다. 따라서 50*7으로 350이다.
   • 1억이 좀 넘지만, 코드화해서 제출했더니 맞았다.

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <map>

using namespace std;

int N, K;
int answer = 0;
vector<string> s;
map<char, bool> m;

void dfs(int k, char c){
    
    if(k>=K){
        int nowCount = 0;
        for(auto i : s){
            bool checked = true;
            for(int j = 4; j<i.size()-4; j++){
                if(!m[i[j]]){
                    checked = false;
                    break;
                }
            }
            if(checked) nowCount++;
        }
        answer = max(answer, nowCount);
        
        return;
    }
    
    for(char i = c+1; i<='z'; i++){
        if(m[i]) continue;
        
        m[i] = true;
        dfs(k+1, i);
        m[i] = false;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N>>K;
    
    if(K<5){
        cout<<0<<endl;
        
        return 0;
    }
    
    for(int i = 0; i<N; i++){
        string tmp;
        cin>>tmp;
        s.push_back(tmp);
    }
    
    m['a'] = true;
    m['n'] = true;
    m['t'] = true;
    m['i'] = true;
    m['c'] = true;
    
    K = K-5;
    
    dfs(0, 'a'-1);
    
    cout<<answer<<endl;
    
    return 0;
}