[백준] 1062 가르침 C++

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

1062번: 가르침

풀이 구상

모든 단어가 anta로 시작하고 tica로 끝나므로 a, n, t, i, c의 5글자는 무조건 배워야 읽을 수 있다. 저 5글자를 모두 배운 후 k - 5개의 글자를 추가로 배워 최대로 읽을 수 있는 단어의 개수를 세면 된다. 백트래킹을 활용하면 구현할 수 있다.

 

1. k가 5보다 작은지 확인하고 작다면 모든 단어를 읽을 수 없으므로 0을 출력하고 종료한다. 또는, 모든 글자를 배울 수 있는 경우 모든 단어를 다 읽을 수 있다. 이 경우 n을 출력하고 종료한다.
2. a, n, t, i, c를 배운 것으로 표시하고 k개의 글자를 배울 때까지 백트래킹을 진행한다.
3. 읽을 수 있는 글자의 개수를 세고 최댓값을 갱신한다.

 

코드 설명

#define LEN 26

bool learn[LEN];
int n, k;
string str[50];
int maxWord = 0;

• learn : 이 글자를 배웠는지 저장한다. index는 a부터 1씩 증가한다.
• str : 단어의 목록이다.
• maxWord : 읽을 수 있는 최대 단어의 개수이다.

 

void backtrack(int idx, int d) {
    if (d == k) {
        int c = 0;
        for (int i = 0; i < n; i++) {
            bool ok = true;
            for (char ch : str[i]) {
                if (!learn[ch - 'a']) {
                    ok = false;
                    break;
                }
            }

            if (ok)
                c++;
        }

        if (c > maxWord)
            maxWord = c;

        return;
    }

    for (int i = idx + 1; i < LEN; i++) {
        if (learn[i])
            continue;

        learn[i] = true;
        backtrack(i, d + 1);
        learn[i] = false;
    }
}

백트래킹 코드이다. 깊이가 k에 도달하면 읽을 수 있는 단어가 몇 개인지 확인하고 최댓값을 갱신한다. 처음에는 idx파라미터 없이 0부터 LEN까지 반복했는데 무의미한 반복이 쌓여 시간 초과가 생긴다. 글자를 알파벳 순서로 배운다고 생각하면 현재 i보다 작은 값은 다시 볼 필요가 없다. 읽을 수 있는 단어를 세는 코드를 다른 함수로 분리하면 더 깔끔한 코드가 될 것 같다.

 

전체 코드

#include <iostream>
#include <string>

using namespace std;

#define LEN 26

bool learn[LEN];
int n, k;
string str[50];
int maxWord = 0;

void backtrack(int idx, int d) {
    if (d == k) {
        int c = 0;
        for (int i = 0; i < n; i++) {
            bool ok = true;
            for (char ch : str[i]) {
                if (!learn[ch - 'a']) {
                    ok = false;
                    break;
                }
            }

            if (ok)
                c++;
        }

        if (c > maxWord)
            maxWord = c;

        return;
    }

    for (int i = idx + 1; i < LEN; i++) {
        if (learn[i])
            continue;

        learn[i] = true;
        backtrack(i, d + 1);
        learn[i] = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> str[i];
    }

    if (k < 5) {
        cout << 0;
        return 0;
    } else if (k == LEN) {
        cout << n;
        return 0;
    }

    learn['a' - 'a'] = true;
    learn['n' - 'a'] = true;
    learn['t' - 'a'] = true;
    learn['i' - 'a'] = true;
    learn['c' - 'a'] = true;
    backtrack(0, 5);

    cout << maxWord;
}