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

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

1062번: 가르침

 

조합을 구현할 수 있는지 없는지에 대한 문제였다. 조합을 구현할 줄 알면 나름 수월하게 풀 수 있다. 하지만 나는 조합을 구현할 줄 몰랐기 때문에 조합을 구현하는 것부터 배웠다. '알고리즘' 파트에 조합, 중복조합, 순열, 중복순열에 대한 글을 정리해놨다. 클릭 바로가기!

​

문제를 읽고 이해하기까지 5분 정도 걸린 것 같다. 이 문제에서 주의할 점은 모든 단어가 'anta'로 시작하고 'tica'로 끝난다는 점이다. 따라서 a, n, t, i, c 다섯 글자가 K 안에 항상 포함된다. 즉, K가 5보다 작으면 정답은 항상 0을 출력, K가 26이면 모든 글자를 배운 경우이므로 N을 출력하면 된다.

​

원리는 간단하다. 조합을 구현하고 K 개의 문자를 선택한 모든 경우에 대해 check() 함수를 돌리면 된다. check() 함수는 선택한 알파벳으로 읽을 수 있는 단어의 개수를 반환해주는 함수다.

​

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

// a n t i c
// 조합으로 선택하면서 k개 선택하면 check로 가능한 단어 개수 검사

char alpha[26];
int sel[26] = {0,};
string *str;
int Max = 0;

int check(int size){
    // 모든 문자열 검색하면서 읽을 수 있는지 검색
    int len, ans = 0;
    for(int i = 0; i < size; i++){
        len = 0;
        for(int idx = 0; idx < str[i].length(); idx++){
            if(sel[(int)(str[i][idx] - 'a')]) len++;
        }
        if(len == str[i].length()) ans++;
    }
    return ans;
}

// 조합 구현
void DFS(int idx, int cnt, int N, int k){
    if(cnt == k){
        Max = max(Max, check(N));
        return;
    }
    
    for(int i = idx; i < 26; i++){
        if(sel[i] == 1) continue;
        sel[i] = 1;
        DFS(i, cnt + 1, N, k);
        sel[i] = 0;
    }
}

int main(){
    int N, K;
    cin >> N >> K;
    
    // 예외처리
    if(K < 5){
        cout << 0 << endl;
        return 0;
    }
    if(K == 26){
        cout << N << endl;
        return 0;
    }
    
    str = new string[N];
    string tmp;
    for(int i = 0; i < N; i++){
        cin >> tmp;
        // 'anta'와 'tica'는 제외하고 저장해준다 
        str[i] = tmp.substr(4, tmp.length() - 8);
    }
    
    sel[(int)('a' - 'a')] = 1;
    sel[(int)('n' - 'a')] = 1;
    sel[(int)('t' - 'a')] = 1;
    sel[(int)('i' - 'a')] = 1;
    sel[(int)('c' - 'a')] = 1;
    
    for(int i = 0; i < 26; i++)
        alpha[i] = 'a' + 0;
    
    DFS(0, 0, N, K - 5);
    
    cout << Max << endl;
    
    delete[] str;
    
    return 0;
}