https://www.acmicpc.net/problem/8111
기본 아이디어는 "1"로 부터 시작해서 DFS로 그 다음 길이의 수들을 다음처럼 탐색해나가는 것이다.
"1"->"11","10"->"111","110","101","100"->...핵심 아이디어는 두가지이다.
- 모듈러 연산
나올수 있는 최대 길이가 100이기 때문에 string으로 처리해야 한다. 또한 배수를 판단하기 위해 연산을 해야하는데, 이는 string으로 표현 된 수가 아닌 수의 나머지로 계산하여 판단한다. (x mod N = (x mod N) mod N... 이기 때문)
나머지의 경우 받을 수 있는 수의 최대값이 20000이기 때문에 int로 처리 가능하다.
- 나머지 R을통한 visited 처리
나머지가 같은 수들은 수가 다르더라도 같은 경우를 처리하게 된다. 그 다음 경우가 모두 R+10, R+11이고 이후에 구한 나머지도 계속해서 같기 때문이다. 여기서는 가장 짧은 수를 찾아야하기 때문에 최초 나온 R만 계산하고, 이후는 isvisited[R]=true로 하여 나머지가 R인 수를 처리하지 않는다.
#include <iostream>
#include <queue>
#include <cstring>
#define ll long long
using namespace std;
int T;
ll N;
bool isVisit[20001];
string solve(ll x){
memset(isVisit, false, sizeof(isVisit));
queue<pair<int, string>> q;
q.push({1, "1"});
while(!q.empty()){
int R = q.front().first;
string tmp = q.front().second;
q.pop();
if(tmp.length()>100) break;
if(isVisit[R]) continue;
isVisit[R]=true;
if(R%x==0) return tmp;
q.push({(R*10)%x, tmp+"0"});
q.push({(R*10+1)%x, tmp+"1"});
}
return "BRAK";
}
int main(){
cin>>T;
for(int i=0; i<T; i++){
cin>>N;
cout<<solve(N)<<'\n';
}
}