백준 8111 0과 1 C++

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

8111번: 0과 1

아이디어만 잘 떠올리면 어렵지 않은 문제였습니다.

 

조건은 다음과 같습니다. 0과 1로 이루어진 수이며 1으로 시작해야합니다. 그리고 자릿수는 100자리 이하인 수 중 입력으로 주어진 애들의 배수인 수를 구하는 것입니다.

예를 들어 17은 17 * 653= = 11101 을 만족합니다. 

만족하는 수가 없다면 BRAK을 출력시킵니다

 

처음에 100자리면 최대 2^100 경우를 나눠야하나 싶었지만 어짜피 가능성 있는 녀석들만 계산해주면 되기 때문에 bfs를 사용하였습니다.

처음에 큐에 {1, "1"} 을 넣습니다. (x = mod N의 결과, s = 원본 스트링)

그 다음부터 스트링에 "0"을 추가하는 경우 { x * 10 % N, s + "0" } 을 큐에 다시 넣고

"1"을 추가하는 경우 {(x * 10 + 1) % N, s + "1"} 을 큐에 넣습니다. 물론 mod N의 결과가 겹치는 것이 나올 것이고, 출력은 아무거나 상관없으므로 mod N의 결과를 체크하여 체킹된 경우는 넘어갑니다.

 

그리하여 mod N의 결과가 0인 경우 해당 스트링이 답 중 하나가 됩니다. (답은 여러 개 가능, 그 중 아무거나)

 

그리고 스트링의 자릿수가 100자리보다 크면 BRAK을 결과에 넣습니다.  

 

코드는 다음과 같습니다.