백준 - 8111번(0과 1) / C++

문제

www.acmicpc.net/problem/8111

8111번: 0과 1

풀이방법:

모듈러 연산을 활용하여 나머지를 체크하면서 bfs를 진행하였다.

첫 숫자가 0이되면 안되므로 1부터 시작하는데

현재숫자를 x라고 했으면 다음 숫자는

각각 x*10 + 0, x*10 + 1 이 된다. 이를 통해 다시 모듈러연산으로 계산을 진행한다.

또한 방문을 했으면 trace라는 배열을 이용하여 여태까지 왔었던 경로를 기억해놨다가

print(0)으로 (모듈러 0, 즉 나누어 떨어질 때 종료하므로) 경로를 역추적하였다. (-1일때 종료)

 

다만,, 한가지 의문점이 있었다. 

문제에서 그러한 숫자가 없으면 "BRAK"을 출력하라고 한다.

힌트에서는 20000이하의 숫자들의 배수는 1과 0으로 전부 표현이 가능하다고 한다.

 

그래서 증명을 해봤다. 수학과 알고리즘 마스터인 친구의 도움을 받았다.

Zz-lion.tistory.com => 친구 블로그 (홍보임;; 암튼 ㄹㅇ 홍보임)

 

결국 20000이내의 숫자들의 배수가 100자리 이하의 0,1로 표현된 숫자로 표현이 가능하다를 증명하진 못했지만,

모든 숫자들의 배수는 0,1로만 이루어진 숫자로 만들 수 있다를 증명하였다. 

제발 누가 왜 20000이내의 숫자 배수의 0,1로 표현된 값이 100자리 이하인지 알려주세요...

 

증명:

 

글씨체가... 죄송합니다 ㅜㅜ

 

코드: