[백준] 1062번 가르침(c++)

문제 링크: https://www.acmicpc.net/problem/1062

문제 및 입출력

문제 접근

완전 탐색으로 구현했다.
단어가 아닌 글자를 가르쳐주는 문제이다.
일단 anta tica는 모든 언어에 들어가는 문자이기 때문에, 무조건 알아야 된다.
그래서 기본적으로 a n i t c 5글자는 알려줘야된다.
K가 5보다 작다면 기본적으로 알아야되는 글자보다 가르칠 수 있는 언어가 작기 때문에 0을 출력해준다.
K가 5랑 동일하다면 배운 언어로 문자를 읽을 수 있는 개수를 구한다.
K > 5보다 크다면, dfs를 실행해준다.
dfs는 배울 수 있는 문자보다 현재 배운 단어가 같거나, 가르칠 수 있는 단어와 현재 배운 단어가 같다면, 배운 단어로 문자를 몇 개 읽을 수 있는 지 체크한다.

코드 구현(c++)

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;
int N, K;
vector<string> words;
vector<char> v;
bool alpha_check[26];
bool picked_alpha[26];
int maxNum = 0;
int check_word(){
    int cnt = 0;
    for(int i = 0 ; i < words.size() ; i++){
        bool isPossible = true;
        for(int j = 4 ; j < words[i].length() - 4 ; j++){
            if(!picked_alpha[words[i][j] - 'a']){
                isPossible = false;
                break;
            }
        }
        if(isPossible) cnt++;
    }
    return cnt;
}
void dfs(int cnt, int n){
    if(cnt == K - 5 || v.size() <= cnt){
        maxNum = max(check_word(), maxNum);
    }
    else{
        for(int i = n ; i < v.size() ; i++){
            if(!picked_alpha[v[i] - 'a']){
                picked_alpha[v[i] - 'a'] = true;
                dfs(cnt+1, i);
                picked_alpha[v[i] - 'a'] = false;
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin >> N >> K;
    
    memset(alpha_check, false, sizeof(alpha_check));
    memset(picked_alpha, false, sizeof(picked_alpha));
    alpha_check['a' - 'a'] = true, alpha_check['n' - 'a'] = true, alpha_check['i' - 'a'] = true, alpha_check['t' - 'a'] = true, alpha_check['c' - 'a'] = true;
    picked_alpha['a' - 'a'] = true, picked_alpha['n' - 'a'] = true, picked_alpha['i' - 'a'] = true, picked_alpha['t' - 'a'] = true, picked_alpha['c' - 'a'] = true;

    for(int i = 0 ; i < N ; i++){
        string temp;
        cin >> temp;
        words.push_back(temp);
        for(int j = 0 ; j < temp.length() ; j++){
            int num = temp[j] - 'a';
            if(!alpha_check[num]){
                alpha_check[num] = true;
                v.push_back(temp[j]);
            }
        }
    }
    if(K - 5 < 0) cout << "0\n";
    else if(K == 5) cout << check_word() << "\n";
    else{
        dfs(0,0);
        cout << maxNum << "\n";
    }
    
}