C++에서 금고 크래킹

암호로 보호되는 상자가 있다고 가정합니다. 암호는 n자리의 시퀀스로, 각 숫자는 처음 k자리 0, 1, ..., k-1 중 하나일 수 있습니다. 따라서 비밀번호를 입력할 때 입력한 마지막 n자리가 올바른 비밀번호와 자동으로 일치됩니다.

예를 들어 올바른 암호가 "563"이라고 가정하고 "285639"를 입력하면 올바른 암호가 입력한 암호의 접미사와 일치하기 때문에 상자가 열립니다. 우리는 입력의 어느 시점에서 상자를 열도록 보장되는 최소 길이의 암호를 찾아야 합니다.

입력이 n =2 및 k =2인 경우 결과는 "01100", "00110", "10011", "11001" 중 하나가 될 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 방문이라는 하나의 집합 정의
• dfs() 함수를 정의합니다. s, k,
• 초기화 i의 경우:=0, i
• temp :=s를 문자열로 연결
• temp가 방문하지 않은 경우 -
  • 방문한 항목에 임시 항목 삽입
  • temp :=인덱스 1에서 끝까지 temp의 하위 문자열 가져오기
  • dfs(temp, k)
  • ret :=ret i를 문자열로 연결

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   set <string> visited;
   string ret;
   string crackSafe(int n, int k) {
      if(n == 1 && k == 1) return "0";
      ret = "";
      string s = "";
      for(int i = 0; i < n - 1; i++){
         s += "0";
      }
      dfs(s, k);
      for(int i = 0; i < n - 1; i++) ret += "0";
      return ret;
   }
   void dfs(string s, int k) {
      string temp;
      for(int i = 0; i < k; i++){
         temp = s + to_string(i);
         if(!visited.count(temp)){
            visited.insert(temp);
            temp = temp.substr(1);
            dfs(temp, k);
            ret += to_string(i);
         }
      }
   }
};
main(){
   Solution ob;
   cout << (ob.crackSafe(2,2));
}

입력

2
2

출력

01100