문제 푼 날짜 : 2021-09-20

문제

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

접근 및 풀이

이 문제는 백트래킹으로 풀되, 가지치기할 조건을 좀 주의해서 생각했어야 했다.
주의해야할 점은 가르칠 알파벳의 갯수가 이미 학습된 단어 "antatica"의 알파벳을 제외해야한다는 것이었다. 문제의 조건에서 이미 a, n, t, i, c는 학습이 되어있는 상태이기 때문이다.
이를 감안하여 아래의 생각대로 코드를 구현하였다.

1. K가 5개 미만이면 아무것도 읽을 수 없으므로 0을 return
2. K가 26개이면 모든 단어를 읽을 수 있으므로 N을 return
3. 학습되지 않은 알파벳 중, 학습할 알파벳을 선택해준다.
4. (K - 5)개 만큼 학습이 완료되면 주어진 단어들을 읽을 수 있는지 체크해준다. (모든 단어가 anta로 시작하고 tica로 끝난다고 했으므로, 이 사이의 알파벳만 체크하도록 하였다.)
5. 읽을 수 있는 단어들의 갯수를 세어주고 최댓값을 업데이트해준다.

코드

// 백준 1062번 : 가르침
#include <iostream>
#include <vector>

using namespace std;

int N, K, ans = -1;
vector<string> v;
bool selected[26] = { false, };

void dfs(int idx, int cnt) {
    if (cnt == K - 5) {
        int ret = 0;
        for (string str : v) {
            bool flag = true;
            if (str.length() > 8) {
                for (int i = 4; i < str.length() - 4; i++) {
                    char ch = str[i];
                    if (!selected[ch - 'a']) {
                        flag = false;
                        break;
                    }
                }
            }
            if (flag) {
                ret++;
            }
        }
        ans = max(ans, ret);
        return;
    }
    for (int i = idx; i < 26; i++) {
        if (selected[i]) {
            continue;
        }
        selected[i] = true;
        dfs(i, cnt + 1);
        selected[i] = false;
    }
}

int main() {
    cin >> N >> K;

    if (K < 5) {
        cout << 0;
        return 0;
    } else if (K == 26) {
        cout << N;
        return 0;
    }

    string already = "antic";
    for (char ch : already) {
        selected[ch - 'a'] = true;
    }

    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        v.push_back(str);
    }
    dfs(0, 0);

    cout << ans;
    return 0;
}

결과

피드백

처음 제출에 시간 초과가 났는데, 학습할 알파벳을 결정할 때 순열이 아닌 조합으로 구현했어야 했는데 이를 순열로 구현해버려서 계속 시간 초과가 났다...
좀 더 문제를 풀 때 신중해야될 것 같다.

순열 조합과 관련된 학습은 https://yabmoons.tistory.com/99 을 참고하였다.