[14584번] 암호 해독

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 부르트 포스

이 문제는 n제한이 20이고, 암호문 길이 제한이 100이고, 사전에 있는 단어의 길이 제한이 20이기에 부르트 포스로 해결이 가능하다.

문제를 접근하기 위해 부르트 포스로 사전 처리를 하기위해 모든 암호문을 만들어 본다.

즉 abcd이면 abcd, bcda, cdab, dacb를 만들 수 있다.

이과정이 cmp를 제작하여 ans에 넣는 과정이고

아래 4중 포문에서 이제 만들어진 모든 ans에 대해 사전에 있는 단어와 비교를 해준다.

이때 kmp를 써도 되지만 시간 복잡도가 크게 무리가 없으므로 kmp를 쓰지 않아도 충분히 문제를 해결 할 수 있다. 

소스 코드 : 

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 79 80 81 82 83 84 85

#include <iostream> #include <cstdio> #include <string.h>   using namespace std;   char cmp[800]; char ans[30][101]; char str[101];   int main() {     // cmp에 abcde...xyzabc...yz...ab..yz..a...z...를 넣어둔다.     char ins = 'a';     int m = 0;     for (int i = 0; i < 26*27; i++)     {         if (i % 26 == 0)         {             ins = 'a';             m = 0;         }         cmp['a' + i] = ins+m;         m++;     }       scanf("%s", str);     int len = strlen(str);       // ans[i]번째에 len만큼의 카이사르 암호를 넣어주며     // 모든 카이사르 암호가 될 수 있는 경우를 만들어준다.     for (int i = 0; i < 26; i++)         for (int j = 0; j < len; j++)         {             cmp['a'] = cmp['a' + i];             ans[i][j] += cmp[str[j] + i];         }       int n;     scanf("%d", &n);       char tmp[30][22];     for (int i = 0; i < n; i++)         scanf("%s",tmp[i]);       // 26가지 종류의 카이사르 암호     for (int i = 0; i < 26; i++)     {         // n가지 종류의 확인 문자         for (int j = 0; j < n; j++)         {             int tlen = strlen(tmp[j]);                          // k는 26가지 종류의 카이사르 암호중 i번째의 pos             for (int k = 0; k <= len-tlen; k++)             {                 int reset = k;                 bool chk = true;                                  // t는 n가지 종류의 확인 문자중 j번째의 pos                 for (int t = 0; t < tlen; t++)                 {                     // ans와 tmp가 서로 다른게 하나라도 있다면                     if (ans[i][k + t] != tmp[j][t])                     {                         chk = false; // 다음 tmp를 보러 간다.                         break;                     }                 }                                  // chk가 계속 true였다면 그것이 정답                 if(chk)                 {                     cout << ans[i];                     return 0;                 }             }         }     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus