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

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

1062번: 가르침

 

문제 해결 알고리즘 

a ~ z 까지 K개를 백트래킹으로 무작위로 골라 배열에 표시한다.

이 때, anta tica가 항상 문자열 앞 뒤에 들어있으므로 a, n, t, i, c는 처음부터 저장해준다.

 

그러고 문자열의 4번째부터 끝에서 4번째까지 배열에 있는 문자열인지 아닌지 검사하고, 모두 있다면 표시해준다.

 

여기서 pos 파라미터를 적절히 써줘야 시간초과를 피할 수 있다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int N, K, result = 0;
int arr[26];
string str[51];

void back_tracking(int cnt, int pos){

    if(cnt == K){

        int temp = 0;
        for(int i=0;i<N;i++){
            
            bool flag = true;
            for(int j=4;j<str[i].size()-4;j++){
                if(!arr[str[i][j] - 'a'])  {
                    flag = false;
                    break;
                }
            }

            if(flag) temp++;
        }

        result = max(result, temp);

        return;
    }

    for(int i=pos;i<26;i++){
        if(arr[i] == 2) continue;
        arr[i] = 1;
        back_tracking(cnt + 1, i + 1);
        arr[i] = 0;
    }
}

int main(){

    arr['a' - 'a'] = 2;
    arr['n' - 'a'] = 2;
    arr['t' - 'a'] = 2;
    arr['i' - 'a'] = 2;
    arr['c' - 'a'] = 2;

    cin >> N >> K;
    for(int i=0;i<N;i++) cin >> str[i];
    
    if(K >= 5) back_tracking(5, 0);

    cout << result;
}