0과 1 - 2
문제
폴란드 왕자 구사과는 다음과 같은 수를 좋아한다.
- 0과 1로만 이루어져 있어야 한다.
- 1이 적어도 하나 있어야 한다.
- 수가 0으로 시작하지 않는다.
- 예를 들어, 101은 구사과가 좋아하는 수이다.
자연수 N이 주어졌을 때, N의 배수이면서, 구사과가 좋아하는 수 중에서 가장 작은 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T(T ≤ 10)가 주어진다.
둘째 줄부터 T개의 줄에는 자연수 N이 한 줄에 하나씩 주어진다.
N은 1,000,000보다 작거나 같은 자연수이다.
출력
각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수 중에서 가장 작은 수를 출력한다.
만약, 그러한 수가 없다면 BRAK을 출력한다.
풀이
우선 8112번(0과 1 - 2)문제가 8111번(0과 1) 문제에서 숫자 범위를 확장시킨 것이기 때문에 8112번의 설명으로 한다.
간단하게 문제를 보면 입력받은 숫자 N에 대해서 N의 배수 중 0과 1로만 이루어진 숫자가 있다면 출력을 한다.
만약 그런 수가 없다면 “BRAK”을 출력한다.
어떻게 접근해야할지 모르겠어서 검색을 해보았는데, BRAK을 별로 신경 쓰지 않고 BFS로 푼 코드가 많았다.
그래서 모든 숫자 N의 배수 중에는 0과 1로 이루어진 수가 반드시 있는 것인가? 찾아봤고, 증명이 가능한 문제였다.
그에 관해서 증명을 해보자.
증명
임의의 숫자 N의 배수 중에는 0과 1로 이루어진 수가 존재한다.
우선 1로만 이루어진 수를 N+1개 만든다.
- 1
- 11
- 111
- 1111
- …
- (1…1) N+1개
이렇게 만든 N+1개의 수에 대해 각각 mod N 연산을 해주면 N+1개의 결과가 나온다.
그런데 mod N의 결과 값은 0~N-1 범위에서 나오기에 총 N가지의 가짓수가 있다.
비둘기집 원리에 따라 N+1개의 mod N의 결과 중 같은 값을 가진 숫자가 반드시 존재하게 되고
각각 1이 A개 이어진 수 (1…1)A, 1이 B개 이어진 수 (1…1)B라고 하자.
A>B라고 하면 (1…1)A - (1…1)B를 했을 때 (1…1)A-B(0…0)B 의 수가 만들어진다.
이 수는 mod N으로 나눴을 때 결과가 0이 되므로 N의 배수이며, 1과 0으로만 이루어진 수이다.
그렇기에 임의의 숫자 N의 배수 중에는 0과 1로 이루어진 수가 존재한다.
앞에서 증명했듯이 항상 0/1로만 이루어진 배수가 존재하니까, BRAK은 신경을 쓰지 않아도 된다.
이제 BFS를 통해서 0과 1을 뒤에 붙이며 계산하는데, 이 때 mod 연산을 이용한 트릭을 쓸 수 있다.
어떤 숫자에 대해 뒤에 0이 붙는다는 것은 10을 곱한다는 것이고, 1은 10을 곱하고 1을 더한 수이다.
mod 연산에서는 (a*b)%N의 결과는 ((a%N)*b)%N와 같기 때문에 계속해서 커지는 수를 관리할 필요 없이
mod N의 결과만 가지고 BFS를 구성할 수 있다.
BFS 분기는 뒤에 0 또는 1이 붙는 것이므로 vis[] 배열은 mod N의 결과 값으로 관리한다.
그 뒤에 0이나 1을 붙여서 생기는 다음 상태는 무조건 (x*10+z)%N으로만 결정된다.
마지막 정답을 출력할 때 queue에다가 string을 그대로 저장해서 시간이나 메모리가 터지지 않을까
살짝 걱정했는데 다행히 924ms로 통과했다.
역추적을 통해서 문자열을 복원하는 방식으로 고치면 아마 개선이 될거라는 생각만 하고 끝.
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
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans=0;
cin >> n;
vector<bool> vis(1000000, 0);
for(int i=0;i<n;i++){
for(int j=0;j<1000000;j++){
vis[j]=0;
}
cin>>m;
string s;
int tmp=1;
queue<pair<int, string>> q;
q.push({tmp%m, "1"});
vis[tmp%m]=1;
while(!q.empty()){
int x=q.front().first;
string st=q.front().second;
q.pop();
if(x==0){
s=st;
break;
}
for(int z=0;z<=1;z++){
t=(x*10+z)%m;
if(!vis[t]){
vis[t]=1;
q.push({t, st+to_string(z)});
}
}
}
cout<<s<<'\n';
}
return 0;
}