BOJ 1062번 가르침

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

github : https://github.com/junho0956/Algorithm/blob/master/1062/1062/%EC%86%8C%EC%8A%A4.cpp

 

 

dfs를 통해서 사용가능한 알파벳의 추가/삭제 연산을 해주면서 완전탐색 하듯이 탐색하였습니다.

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
 
bool visit[26];
int N, K, ans;
vector<string> v;
 
void solve(int al, int pk) {
 
    if (pk == K) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            bool temp = true;
            for (int j = 4; j < v[i].size() - 4; j++) {
                if (visit[v[i][j]-'a'] == false) {
                    temp = false;
                    break;
                }
            }
            if (temp) cnt++;
        }
        ans = max(ans, cnt);
        return;
    }
 
    for (int i = al; i < 26; i++) {
        if (!visit[i]) {
            visit[i] = 1;
            solve(i, pk + 1);
            visit[i] = 0;
        }
    }
 
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    visit['a' - 'a'] = visit['c' - 'a'] = visit['t' - 'a'] = visit['i' - 'a'] = visit['n' - 'a'] = true;
 
    cin >> N >> K;
    if (K < 5) ans = 0;
    else if (K == 26) ans = N;
    else {
        string str;
        for (int i = 0; i < N; i++) {
            cin >> str;
            v.push_back(str);
        }
 
        solve(0, 5);
    }
 
    cout << ans;
    return 0;
}