[백준] 1062 - 가르침

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

1062번: 가르침

 처음엔 좀 쉽게 생각했다. ASCII 코드에 대한 이해도와 입력되는 문자열에서 나타나는 알파벳의 발생 횟수를 기억해놓고 이를 내림차순으로 정렬하면 배우는 글자 수에 따라 읽을 수 있는 단어 갯수를 알아낼 줄 알았다. 그런데 해보니까 아니네...

 이번 문제에서 필요한 지식은 이정도가 될것 같다.

1. ASCII 코드에 대한 이해를 통해 알파벳 별 출현 여부를 bit masking하여 배열에 저장하는 법.
2. 확률 통계에서 조합에 대한 간단한 이해 (순서와 상관이 있는 경우의 수는 순열, 순서와 상관이 없으면 조합)
3. 조합에 대한 이론을 DFS(깊이 우선 탐색)으로 구현하는 법

#include <iostream>
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int N, K;
bool visited[30];
char input[51][17];
int readMax = 0;

void solve(int start, int count)
{
    if (count == K)
    {
        int canReadCnt = 0;

        for (int i = 0; i < N; ++i)
        {
            bool canRead = true;
            for (int j = 0; j < strlen(input[i]); ++j)
            {
                if (visited[input[i][j] - 'a'] == false)
                {
                    canRead = false;
                    break;
                }
            }
            if (canRead)
            {
                canReadCnt += 1;
            }
        }
        if (canReadCnt > readMax)
        {
            readMax = canReadCnt;
        }
        return;
    }

    for(int i=start; i<26; ++i){
        if(visited[i] == false){
            visited[i] = true;
            solve(i, count + 1);
            visited[i] = false;
        }
    }
}

int main()
{
    memset(visited, false, sizeof(visited));

    scanf("%d%d", &N, &K);
    for (int i = 0; i < N; ++i)
    {
        scanf("%s", &input[i]);
    }

    if (K < 5)
    {
        printf("0\n");
    }
    else if (K >= 26)
    {
        printf("%d\n", N);
    }
    else
    {
        K -= 5;
        visited['a' - 'a'] = true;
        visited['c' - 'a'] = true;
        visited['i' - 'a'] = true;
        visited['n' - 'a'] = true;
        visited['t' - 'a'] = true;
        solve(0, 0);

        printf("%d\n", readMax);
    }

    return 0;
}