[백준 1062] 가르침 (C++)

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

 

 

Back tracking (백트래킹)

 

k개의 글자를 가르칠 수 있을 때, 주어진 N개의 문자열 중 최대 몇개를 읽을 수 있게 할 수 있는지 출력하는 문제

단, N개의 문자열은 모두 anta로 시작하고 tica로 끝난다. = 최소 acnti 는 가르칠 수 있어야 단어를 한개라도 가르칠 수 있음

 

접근 방법

처음에는 N개의 문자열을 dfs로 순회하면서 읽을 수 있는 문자열 그룹의 경우를 모두 확인하려고 했는데,

26개의 알파벳 중 가르칠 문자 그룹의 모든 경우에 대해서 각각 그룹이 읽을 수 있는 문자열의 갯수를 구하면서

최댓값을 찾는 것이 시간초과가 나지 않는 풀이법이었다.

 

N이 50개까지 밖에 안가지만 그래도 시간복잡도가 26에 비해서는 커질 수 밖에 없는듯

 

풀이법은

1. anta_tica를 제외한 범위만 추출해서 list에 N개의 문자열을 담아둔다.

2. mask라는 가르칠 문자열에 대해 true 표시가 되어있는 26개의 bool 배열을 만들고, acnti에 대해서는 true로 초기화해둔다 (acnti는 최소 요건이기 때문)

3. acnti를 포함하여 k개의 문자에 대해 true라고 표시되어있는, 알파벳을 나타내는 bool배열을 가능한 모든 경우에 대해 만들어서 masks라는 2차원배열에 저장해야한다.

3.1. cnt로 가르친 문자 개수를 추적하고, 모든 알파벳을 순회하며 아직 가르칠 문자에 포함되지 않은 단어면 포함하는 경우와, 포함하지 않는 경우에 대해서 재귀함수를 각각 호출한다.

3.2. 다음 확인할 알파벳 번호를 나타내는 i가 26 즉 z까지 다 확인했을 경우, 그냥 재귀함수를 종료하거나, cnt(가르칠 문자수)가 k개가 됐을 경우 해당 mask 경우를 masks에 추가한다.

4. 이렇게 모든 경우가 masks에 모이면, masks에 담긴 배열을 하나하나 확인하면서 해당 글자 그룹으로 몇개의 단어를 읽을 수 있는지 확인한다.

5. 읽을 수 있는 단어 수가 answer에 담겨있는 값보다 클 경우 answer에 담는다.

 

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

vector<vector<bool>> masks;

void dfs(int i, int k, int cnt, vector<bool> mask){
    if(i <= 26) {
        if(cnt == k){
            masks.push_back(mask);
        } else {
            if(i == 26){
                return;
            }
            if(!mask[i]){
                vector<bool> _mask(mask.begin(), mask.end());
                // 글자 포함하기
                _mask[i] = true;
                dfs(i+1, k, cnt+1, _mask);
            }
            // 포함 안함
            dfs(i+1, k, cnt, mask);
        }
    }
}

int main() {
    int N, K;
    cin >> N >> K;
    
    if(K < 5){
        cout << 0;
        return 0;
    }
    
    vector<string> list;

    for(int i = 0 ; i < N ; i++){
        string s;
        cin >> s;
        list.push_back(s.substr(4, s.size()-8));
    }
    
    vector<bool> mask(26, false);
    mask['a'-'a'] = true;
    mask['c'-'a'] = true;
    mask['n'-'a'] = true;
    mask['t'-'a'] = true;
    mask['i'-'a'] = true;
    dfs(1, K, 5, mask);
    
    int answer = 0;
    for(vector<bool> m: masks){
        // 이 글자들로 단어 몇개 읽을 수 있는지 확인
        int cnt = 0;
        for(string word: list){
            bool isReadable = true;
            for(char ch: word){
                if(!m[ch-'a']){
                    isReadable = false;
                    break;
                }
            }
            if(isReadable)
                cnt++;
        }
        if(answer < cnt){
            answer = cnt;
        }
    }
    
    cout << answer;
    
    return 0;
}