백준2595 배수

작성일 | In

문제 링크

  • http://icpc.me/2595

문제 출처

  • 2005 KOI 지역본선 고등부 5번

사용 알고리즘

  • BFS

풀이

원래 문제를 풀기 전에 아래 문제를 먼저 풀어봅시다.

1과 0만 사용하여 자연수 N의 배수를 하나 찾으시오.

1과 0만 사용하여 N의 배수를 찾는 것은, 0에서 시작해서 (×10) 연산과 (×10+1) 연산만 적절히 이용하여 N의 배수를 찾으라는 것을 의미합니다.
바꿔말하면 (×10 mod N) 연산과 (×10+1 mod N) 연산을 적절히 사용하여 0으로 만들라는 것을 의미합니다.

그러므로 정점 N개짜리 그래프를 만들어서, x번 정점에서 (10x mod N)번 정점으로 가는 간선 하나, (10x+1 mod N)번 정점으로 가는 간선 하나를 만들어서 BFS 등을 통해 0으로 가는 경로를 찾으면 됩니다.

사용 가능한 숫자가 달라져도 똑같이 풀 수 있습니다.

이제 원래 문제를 풀어봅시다. 사용하는 숫자의 종류를 최소화하고, 수의 크기도 최소화해야 합니다.

사용할 숫자들을 정했다면 수의 크기를 최소화하는 것은 간선 순서를 오름차순으로 한 뒤 BFS를 돌리는 것으로 쉽게 해결할 수 있습니다.
N 범위가 작기 때문에 $2^{10}$가지의 가능한 모든 숫자 조합에 대해 모두 BFS를 돌려보는 것으로 문제를 해결할 수 있습니다.

전체 코드

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
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

int n;
vector<int> comb[1 << 10];
int prv[70707];
int mv[70707];
int chk[70707];

int valid(int bit){
    queue<int> q;
    for(auto j : comb[bit]) if(j) {
        int i = j % n;
        chk[i] = 1; q.push(i); mv[i] = j;
    }
    while(q.size()){
        int v = q.front(); q.pop();
        if(!v) return 1;
        for(auto j : comb[bit]){
            int i = (v * 10 + j) % n;
            if(!chk[i]) {
                prv[i] = v; mv[i] = j; chk[i] = 1; q.push(i);
            }
        }
    }
    return 0;
}

void solve(){
    cin >> n;
    vector<string> v;
    int cnt;
    for(int i=0; i<(1 << 10); i++){
        memset(prv, -1, sizeof(int) * (n+10));
        memset(chk, 0, sizeof(int) * (n+10));
        if(v.size() && cnt < comb[i].size()) break;
        if(valid(i)){
            string s;
            for(int j=0; j!=-1; j=prv[j]) s += char(mv[j] + '0');
            reverse(all(s));
            v.push_back(s);
            cnt = comb[i].size();
        }
    }
    sort(all(v), [](const string &a, const string &b){
        if(a.size() != b.size()) return a.size() < b.size();
        return a < b;
    });
    cout << v[0] << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    for(int bit=0; bit<(1<<10); bit++){
        for(int i=0; i<10; i++) if(bit & (1 << i)) comb[bit].push_back(i);
    }
    sort(comb, comb+1024, [](const vector<int> &a, const vector<int> &b){
        return a.size() < b.size();
    });
    int t = 1;
    while(t--) solve();
}