[백준 1062] 가르침

[백준 1062] 가르침

문제 링크

using namespace std;
int N, K, n;
int answer;
map<char, int> m;
vector<string> learn;
set<char> s;
vector<char> v;
void init() {

    for(char i='a'; i<='z'; i++){
        m[i] = 0;
    }
    m['a'] = 1;
    m['n'] = 1;
    m['t'] = 1;
    m['i'] = 1;
    m['c'] = 1;
}
void input() {
    init();
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        string target = str.substr(4);
        target = target.replace(target.find("tica"), 4, "");
        learn.push_back(target);
        for (int j = 0; j < target.size(); j++) {
            if (m[target[j]])
                continue;
            else {
                s.insert(target[j]);
            }
        }
    }
}

void check() {
    int cnt = 0;

    for (int i = 0; i < learn.size(); i++) {
        string cmp = learn[i];
        int flag = 1;
        for (int j = 0; j < cmp.length(); j++) {
            if (!m[cmp[j]]) {
                flag = 0;
                break;
            }
        }
        if (flag) cnt++;
    }

    answer = max(answer, cnt);
}
void dfs(vector<char>& v, int idx, int cnt) {
    if(cnt > n) return;
    if(K-5 < 0) return;
    if(cnt == n){
        check();
    }

    for (int i = idx; i < v.size(); i++) {
        if (!m[v[i]]) {
            m[v[i]] = 1;
            cnt++;
            dfs(v, i + 1, cnt);
            cnt--;
            m[v[i]] = 0;
        }
    }
}
void solve() {
    n = K - 5;  //배울 수 있는 갯수
    int answer = 0;

    v.assign(s.begin(), s.end());  // 가르쳐야 할 단어들
    if(v.size() < n) n = v.size();

    dfs(v, 0, 0);
}
int main() {
    input();
    solve();
    cout << answer << endl;

    return 0;
}

• 백트래킹으로 푸는 문제이다.
• anta, tica를 제외한 문장들을 벡터에 넣는다.
• 이 과정에서 set에 배워야하는 문자들을 넣는다.
• 그리고 a, n, t, i, c 는 이미 배운 문자이므로 1로 처리 해 준다.
• K-5가 배울 수 있는 문자의 갯수이다.
• 배울 수 있는 문자의 갯수만큼 센 뒤, check()함수를 통해 answer를 업데이트 시켜준다.
• 이렇게 하면, 배워야 하는 문자들의 모든 경우의 수를 탐색할 수 있다.