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

[문제]

1062번: 가르침 (acmicpc.net)

1062번: 가르침

[문제 풀이]

백트래킹을 이용해서 문자열을 만족할 수 있는지를 파악하는 문제였다.

k가 만약에 5개 미만이라면 anta, tica 조차 만들 수 없으니 당연히 0을 반환하도록 하고

5개 이상이라면 visited배열을 이용해서 a, c, i, n, t 5개를 모두 1로 바꾼뒤에

백트래킹을 이용해서 조합을 만들면서 다른 알파벳들을 방문처리 하고 입력받은 string들이 모두 visited배열에서 방문을 했었는지를 확인하면 생각보다 쉽게 풀릴 수 있다.

[회고]

백트래킹 작업을 할때

for(int i = 1;i<=26;i++)

로 두었다가 계속해서 시간초과가 일어나는 부분이 생겨서 인터넷을 보고 참고해서

for(int i = idx;i<=26;i++)

로 바꿨더니 시간초과가 안일어났다.

생각해보면 계속해서 for문에서 1부터 차례대로 갈텐데 idx로 시작을 하게 만든다면 이와 같은 부분에서 시간을 아낄 수 있으니 시간초과가 일어나지 않을것이다.

앞으로도 이와 같은 부분에 주의를 하자.

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
#define endl "\n"
using namespace std;

vector<string > anta;
int visited[28];
int n,k;
int answer;

//백트래킹 이용해서 26개중에서 k개 선발하기.
void backTrack(int idx,int cnt){
    if(cnt == k){
        int count = 0;
        bool flag = true;
        for(int i = 0;i<anta.size();i++){
            flag = true;
            for(int j = 4;j<anta[i].size() - 4;j++){
                // cout<<"anta : "<<anta[i][j] - 'a' + 1<<" ";
                if(visited[anta[i][j] - 'a' + 1] == 0){
                    flag = false;
                    break;
                }
            }
            // cout<<endl;
            if(flag == true){
                count++;
            }
        }
        answer = max(answer,count);
        return;
    }
    
    for(int i = idx;i<=26;i++){
        if(visited[i] == 0){
            visited[i] = 1;
            backTrack(i,cnt + 1);
            visited[i] = 0;
        }
    }
    
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>k;
    for(int i = 0;i<n;i++){
        string s;
        cin>>s;
        anta.push_back(s);
    }
    //5미만이면 나올 수 있는 값이 없다.
    if(k<5){
        cout<<0<<endl;
        return 0;
    }
    else if(k >= 26){
        cout<<n<<endl;
        return 0;
    }
    //5이상이라면
    visited[1] = 1;
    visited[3] = 1;
    visited[9] = 1;
    visited[14] = 1;
    visited[20] = 1;

    k = k - 5;

    backTrack(0,0);

    cout<<answer<<endl;

    return 0;
}