[백준] 1062번 가르침 C++ 코드

코드1

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int n,k,cnt,a[26];
vector<string> v;
string s;

void FASTIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
// 단어 몇 개를 읽을 수 있는지 확인하는 과정
int go() {
  int temp = 0;
  bool check;
  for(string voca : v) {
    check = true;
    for(char sp : voca) {
      if(a[sp-'a'] == 0) {
        check = false;
        break;
      }
    }
    if(check) temp++; // 모든 스펠링을 읽을 수 있으면 1 증가
  }
  return temp;
}
// 배울 알파벳 조합 구하기
void dfs(int start, int cnt2) {
  // 조건 충족
  if(cnt2 == k-5) {
    cnt = max(cnt, go());
    return;
  }
  for(int i = start; i < 26; i++) {
    if(a[i]) continue;
    a[i] = 1; // 알파뱃 추가
    dfs(i, cnt2+1); // 탐색
    a[i] = 0; // 탐색이 끝나면 다음 경우의 수를 찾기 위해 원상복구
  }
  return;
}

int main() {
  FASTIO();
  cin >> n >> k;
  // a,n,t,c,i는 꼭 배워야하므로 체크
  a[0] = 1;
  a['n'-'a'] = 1;
  a['t'-'a'] = 1;
  a['c'-'a'] = 1;
  a['i'-'a'] = 1;
  
  for(int i = 0; i < n; i++) {
    cin >> s;
    v.push_back(s); // 단어 리스트에 추가
  }
  // 배울 수 있는 것이 5개 미만이면 0을 출력
  if(k < 5) {
    cout << 0 << '\n';
    return 0;
  }
  dfs(0,0);
  cout << cnt << '\n';
  return 0;
}

처음에 조합으로 vector에 모든 경우의 수를 모으려고 했지만 메모리가 폭발해버렸다. 그래서 dfs를 이용해 경우의 수를 찾아 문제를 해결했다.