[BOJ][백트래킹][골4]][1062] 가르침

문제 링크

문제 링크

풀이

알고리즘

N자리 K진수를 적용해서 해결하는 문제입니다. 선택한다/안한다의 방법을 적용합니다.

[이론][완전탐색][N자리 K진수] Chapter 2를 확인해보세요.

정답 코드

#include <bits/stdc++.h>

#define MAX 26
using namespace std;
typedef long long ll;

int n = 0, k = 0; //N:배열의 길이 , K: 진수
vector<string> input(60);
int v[MAX];
bool visited[MAX];
int ans = 0;

// depth번째로 가르칠 문자를 결정한다
void recur(int depth, int start) {
  if (depth == k) {
    if (!visited['a' - 'a']) return;
    else if (!visited['n' - 'a']) return;
    else if (!visited['t' - 'a']) return;
    else if (!visited['i' - 'a']) return;
    else if (!visited['c' - 'a']) return;
    int t_ans = 0;
    for (int i = 0; i < n; i++) {
      int sLen = input[i].size();
      bool flag = true;
      for (int j = 0; j < sLen; j++) {
        if (!visited[input[i][j] - 'a']) {
          flag = false;
          break;
        }
      }
      if (flag) {
        t_ans++;
      }
    }
    ans = max(ans, t_ans);
    return;
  }

  for (int i = start; i < MAX; i++) {
    if (visited[i]) continue;
    visited[i] = true;
    recur(depth + 1, i + 1);
    visited[i] = false;
  }
}

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> input[i];
    input[i] = input[i].substr(4, input[i].size() - 8);
  }
  recur(0, 0);
  cout << ans << "\n";
  return 0;
}

Success Notice: N 자리 K진수 개념을 사용한 문제를 풀어봤습니다. 수고하셨습니다.