[1062번] 가르침

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 재귀

단순 재귀를 통해 문제 해결이 가능하다.

단 이때 "anta"로 시작되고, "tica"로 끝난다 하였으니

"a n t i c"는 항상 배워야 하는 단어이니 이 단어를 포함하고난 후 남은 k의 개수로 재귀를 돌리면 문제를 해결 할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

#include <iostream> #include <cstdio> #include <string> #include <algorithm>   using namespace std;   int word[200]; string str[52]; int ans;   void useAlphabet(int n, int k, char start) {     if (k < 0)         return;       if (k == 0)     {         int val = 0;         for (int i = 0; i < n; i++)         {             int len = str[i].size();             int cnt = 0;             for (int j = 0; j < len; j++)             {                 if (word[str[i][j]])                     cnt++;                 else                     break;             }             if (cnt == len)                 val++;         }           ans = max(ans, val);           return;     }       for(int i = start; i <= 'z'; i++)         if (!word[i])         {             if (k > 'z' - i + 1)                 continue;             word[i] = true;             useAlphabet(n, k - 1, i + 1);             word[i] = false;         } } int main() {     int n, k;     cin >> n >> k;       for (int i = 0; i < n; i++)     {         cin >> str[i];         str[i].erase(str[i].begin(), str[i].begin() + 4);         str[i].pop_back();         str[i].pop_back();         str[i].pop_back();         str[i].pop_back();     }          word['a'] = true;     word['c'] = true;     word['i'] = true;     word['n'] = true;     word['t'] = true;     useAlphabet(n, k - 5, 'a');          cout << ans;          return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus