[BOJ/1062/C++] 가르침

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

문제

• 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다.
• 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다.
• 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.
• 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다.

남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

조건

• 첫째 줄에 단어의 개수 N과 K가 주어진다.
• N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다.
• 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다.
• 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다.
• 모든 단어는 중복되지 않는다.

풀이

이 문제는 시간초과가 난다는 것을 알고 난 후, 어떻게 시간을 줄여나갈까?를 생각하면서 풀어가는 문제였던것 같다. 푸는방법 자체는 조합의 구현 =>단어 탐색으로 간단한 편이다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 이 조건으로 인해서 많은 가짓수를 칠 수 있게 된다.

• a,t,n,i,c 5가지 글자는 꼭 알아야한다. => K<5이면 , 0 출력
• anta 앞 4글자와 뒤 tica는 꼭 볼 필요가 없다. => 앞 4글자, 뒤 4글자 자르고, 중간글자만 보기
• K개를 항상 K-5개만 탐색할 수 있다. => atnic가 무조건 있다고 생각하고, 경우의 수 돌기.

조합을 구현하는 방법은 여러가지가 있지만, 나는 아래와 같이 구현했다. 여러가지 방법 중에 나는 아래가 제일 직관적으로 잘 떠올라서 보통 아래와같이 구현한다.

	bool visited[방문할 갯수]
    
    void func(int idx,int depth){
    	if(depth == K){
        	...
           	return;
        }
    	for(int i=idx;i<N;i++){
        	if(visited[i])
            	continue;
            visited[i] = true;
            func(i,depth+1);
            visited[i] = false;
        }
    }

코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define MAX_K 26

using namespace std;

const int A = 0;
const int T = 19;
const int C = 2;
const int n = 13;
const int I = 8;

int N, K;
int mx;
string words[50];
bool alphabet[MAX_K];

// 26개 중에 K개를 선택해서 가르쳐 준뒤 ,단어들을 다 체크해보자.
int chk_words()
{
  int cnt = 0;
  for (int i = 0; i < N; i++)
  {
    bool flag = true;
    for (int j = 0; j < words[i].size(); j++)
    {
      // 못읽는 글자가 하나라도 있다면 다음 글자를 봐야한다.
      if (alphabet[words[i][j] - 'a'] == false)
      {
        flag = false;
        break;
      }
    }
    if (flag)
      cnt++;
  }
  return cnt;
}

void selectWord(int idx, int depth)
{
  if (depth == K)
  {
    mx = max(mx, chk_words());
    return;
  }
  for (int i = idx; i < MAX_K; i++)
  {
    if (alphabet[i])
      continue;
    alphabet[i] = true;
    selectWord(i, depth + 1);
    alphabet[i] = false;
  }
}

int main()
{
  fastio;
  cin >> N >> K;
  // anta tica로 이루어져 있기 때문에, 최소 5개의 단어는 알아야한다.
  if (K < 5)
  {
    cout << 0 << '\n';
    return 0;
  }
  // 다 읽을 수 있다.
  else if (K == 26)
  {
    cout << N << '\n';
    return 0;
  }
  // 5개를 굳이 다 읽을 필요가 있을까?
  // 앞 4글자와 뒷 4글자는 필수로 읽는다고 치고, 중간 글자만 확인하자.
  K -= 5;
  for (int i = 0; i < N; i++)
  {
    cin >> words[i];
    // parsing
    words[i] = words[i].substr(4, words[i].size());
    for (int j = 0; j < 4; j++)
      words[i].pop_back();
  }

  alphabet[A] = true;
  alphabet[T] = true;
  alphabet[n] = true;
  alphabet[I] = true;
  alphabet[C] = true;

  selectWord(0, 0);
  cout << mx << '\n';
  return 0;
}