[BOJ] 백준 1062 가르침 c++ (백트래킹)

문제 출처 : https://www.acmicpc.net/problem/1062

1062번: 가르침

---

풀이

• 남극의 언어가 anta로 시작되고 tica로 끝난다 -> a c i n t는 필수로 가르쳐야 한다.
• 즉 K가 5 미만이라면 0을 출력하면 된다.
• a c i n t는 디폴트로 학습시킨다.
• 입력 단어에서 anta, tica를 빼고 저장해 시간을 줄일 수 있다.

string str = "";
for(int i = 0; i < N; i++){
    cin >> str;
    v.push_back(str.substr(4, str.length() - 8));
}
if(K < 5){
    cout << 0 << '\n';
    return 0;
}

• dfs로 K-5만큼 알파벳을 뽑아 계산해주면 된다! 이때 백트래킹을 사용하자
• 이때 i = idx로 하지 않고 0부터 돌리면 이미 체크했던 부분을 다시 체크해 시간초과가 발생하므로 주의하자

// void dfs(int idx, int remain) remain : 남은 가르칠수 있는 알파벳

for(int i = idx; i < 26; i++){
    if(alpha[i]) continue;
    alpha[i] = true;
    dfs(i, remain - 1);
    alpha[i] = false;
}

---

코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int N, K;
bool alpha[26];
int ans;
vector<string> v;

void dfs(int idx, int remain){
    if(!remain){
        int cnt = 0;
        for(string elem : v){
            bool flag = true;
            for(char ch : elem){
                if(!alpha[ch - 'a']){
                    flag = false;
                    break;
                }
            }
            if(flag) cnt++;
        }
        ans = max(ans, cnt);
        if(ans == N){
            cout << N << '\n';
            exit(0);
        }
        return;
    }
    for(int i = idx; i < 26; i++){
        if(alpha[i]) continue;
        alpha[i] = true;
        dfs(i, remain - 1);
        alpha[i] = false;
    }
}

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

    cin >> N >> K;
    string str = "";
    for(int i = 0; i < N; i++){
        cin >> str;
        v.push_back(str.substr(4, str.length() - 8));
    }
    if(K < 5){
        cout << 0 << '\n';
        return 0;
    }
    // a c i n t 필수
    alpha[0] = true; alpha[2] = true; alpha[8] = true;
    alpha[13] = true; alpha[19] = true;    

    dfs(0, K-5);
    cout << ans << '\n';
    return 0;
}