백준 1062 가르침 (C++)

1062번: 가르침

백트래킹을 이용한 문제이다. 입력으로 주어지는 문자에 앞과 뒤에는 고정된 문자 anta와 tica가 존재한다. 그렇기에 5개의 문자는 고정으로 배워야하므로 5 미만의 K는 모두 0을 출력해주었다. dfs를 돌면서 문자 하나씩 true로 바꿔주며 문자열을 모두 확인해주면서 읽을 수 있는 단어를 카운트를 해주고 최댓값을 구해 출력해주었다.
어렵지 않게 풀 수 있었던 문제였다. dfs를 응용하는 법에 대해 잘 알 수 있었던 문제였다. 다른 사람의 풀이를 보니 겹치는 단어를 제거함으로써 시간을 많이 줄여주는 방식도 있다는 것을 알게되었다. 이러한 방식도 인지해두어야 겠다.

#include <iostream>
#include <algorithm>

using namespace std;

int N, K, result = 0;
string s[50];
string word[50];
bool check[26];

void dfs(int depth, int k) {
    if (k > K) return;

    int count = 0;

    for (int i = 0; i < N; i++) {
        bool tf = true;
        for (int j = 0; j < s[i].size(); j++) {
            if (check[s[i][j] - 'a']) continue;

            tf = false;
            break;
        }

        if (tf) count++;
    }

    if (k == K) {
        result = max(count, result);
        return;
    }

    for (int i = depth; i < 26; i++) {
        if (check[i]) continue;
        check[i] = true;
        dfs(i, k + 1);
        check[i] = false;
    }
}

void solution() {
    if (K < 5) {
        cout << 0;
        return;
    }

    check['a' - 'a'] = true;
    check['n' - 'a'] = true;
    check['t' - 'a'] = true;
    check['i' - 'a'] = true;
    check['c' - 'a'] = true;

    dfs(0, 5);

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;

    for (int i = 0; i < N; i++) {
        cin >> s[i];
        s[i] = s[i].substr(4, s[i].size() - 8);
    }

    solution();

    return 0;
}