[백준 1062] 가르침 (C#, C++) - soo:bak

문제 링크

1062번 - 가르침

설명

K개의 글자를 가르쳤을 때 읽을 수 있는 단어의 최대 개수를 구하는 문제입니다. 모든 단어는 anta로 시작해 tica로 끝나므로 a, c, i, n, t 다섯 글자는 반드시 가르쳐야 합니다.

접근법

K가 5 미만이면 필수 글자조차 가르칠 수 없으므로 0을 출력합니다. K가 26이면 모든 글자를 가르칠 수 있으므로 N을 출력합니다.

각 단어에서 앞의 anta와 뒤의 tica를 제외한 중간 부분의 글자들을 비트마스크로 저장합니다. 필수 다섯 글자를 이미 배운 상태에서 나머지 21개 글자 중 K-5개를 조합으로 선택합니다.

조합이 완성될 때마다 각 단어의 글자가 모두 선택된 글자에 포함되는지 확인하여 읽을 수 있는 단어 수를 셉니다. 모든 조합 중 최댓값을 출력합니다.

---

Code

C#

using System;

class Program {
  static int n, k, need, answer;
  static int[] words;

  static void Dfs(int idx, int picked, int mask) {
    if (picked == need) {
      var cnt = 0;
      for (var i = 0; i < n; i++)
        if ((words[i] & ~mask) == 0) cnt++;
      if (cnt > answer) answer = cnt;
      return;
    }
    for (var i = idx; i < 26; i++) {
      if ((mask & (1 << i)) != 0) continue;
      Dfs(i + 1, picked + 1, mask | (1 << i));
    }
  }

  static void Main() {
    var first = Console.ReadLine()!.Split();
    n = int.Parse(first[0]);
    k = int.Parse(first[1]);
    words = new int[n];

    if (k < 5) { Console.WriteLine(0); return; }
    if (k == 26) { Console.WriteLine(n); return; }

    var baseMask = 0;
    foreach (var ch in "acint")
      baseMask |= 1 << (ch - 'a');

    for (var i = 0; i < n; i++) {
      var s = Console.ReadLine()!;
      var core = s.Substring(4, s.Length - 8);
      var mask = 0;
      foreach (var ch in core)
        mask |= 1 << (ch - 'a');
      words[i] = mask;
    }

    need = k - 5;
    Dfs(0, 0, baseMask);
    Console.WriteLine(answer);
  }
}

C++

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

typedef vector<int> vi;

int n, k, need, best;
vi words;

void dfs(int idx, int picked, int mask) {
  if (picked == need) {
    int cnt = 0;
    for (int w : words)
      if ((w & ~mask) == 0) ++cnt;
    best = max(best, cnt);
    return;
  }
  for (int i = idx; i < 26; i++) {
    if (mask & (1 << i)) continue;
    dfs(i + 1, picked + 1, mask | (1 << i));
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> k;
  if (k < 5) { cout << 0 << "\n"; return 0; }
  if (k == 26) { cout << n << "\n"; return 0; }

  int baseMask = 0;
  for (char c : string("acint")) baseMask |= 1 << (c - 'a');

  words.resize(n);
  for (int i = 0; i < n; i++) {
    string s; cin >> s;
    string core = s.substr(4, s.size() - 8);
    int mask = 0;
    for (char c : core) mask |= 1 << (c - 'a');
    words[i] = mask;
  }

  need = k - 5;
  dfs(0, 0, baseMask);
  cout << best << "\n";

  return 0;
}