배수( BOJ 2595 )

문제 : https://www.acmicpc.net/problem/2595

2595번: 배수

 

문제 파악하기

30,000 이하의 자연수인 N의 배수 중 가장 적은 개수의 숫자로 이루어진 가장 작은 배수를 찾는 문제입니다. 예를 들어 125의 배수는 무한히 많은 숫자가 있지만, 그 중에서 가장 적은 개수의 숫자로 이루어진 가장 작은 배수는 500을 의미합니다. 이 문제는 결국 1개 또는 2개의 숫자로 이루어진 N의 배수가 있는지, 그리고 그 중에서 가장 작은 숫자가 무엇인지 구하는 문제입니다. 참고로 모든 정수는 1개 혹은 2개의 숫자로 이루어진 배수를 무조건 가지고 있습니다.

 

문제 해결하기

우리는 그렇다면 0~9까지 숫자 중 2가지를 뽑아서 배수를 만들어볼 수 있습니다. 뽑은 2개의 수로 이루어진 배수를 만든 후에는 지금까지 구한 배수 중 가장 작은 배수를 찾기만 하면 됩니다. 여기서 중요한 점은 1개의 정수로도 배수를 만들 수 있다는 점을 놓쳐서는 안됩니다. 그리고 우리가 구한 숫자가 엄청 커질 수 있기에 long long int형이 아닌 string형을 사용하면 탐색을 할 때 용이할 수 있습니다.

 

2개의 정수로 이루어진 배수를 만드는 방법은 비둘기집의 원리를 이용합니다. 지금까지 만든 숫자를 N으로 나눠 나머지를 구한 다음, 이전까지 구한 적이 있는지 없는지 확인합니다. 나머지는 항상 0부터 (N-1)까지 총 N개만 있기 때문에 한번 나온 나머지는 더이상 탐색할 필요가 없습니다. 그리고 지금까지 나온 나머지의 경로를 저장한 뒤, 배수를 찾았을 때 역추적을 하면 2개의 숫자로 이루어진 배수를 찾을 수 있습니다.

 

이렇게 배수를 만든 후에는 string 타입의 두 숫자를 비교해야 합니다. 비교 시 우선은 길이를 사용하여 비교할 수 있으며, 길이가 동일한 경우에는 앞자리 숫자부터 비교하면서 대소관계를 알아냅니다. 이렇게 구할 수 있는 모든 배수를 구한 후, 가장 작은 배수를 출력하면 우리가 원하는 결괏값을 얻을 수 있습니다.

 

소스코드

 

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 30010
using namespace std;
 
int N;
 
int tmpi, reti;
string tmp, ret;
 
bool isBig(string a, string b) {
    if(a.length() < b.length()) return 1;
    else if(a.length() > b.length()) return 0;
    else {
        for(int i=0;i<a.length();i++) {
            if(a[i] > b[i]) return 0;
            else if(a[i] < b[i]) return 1;
        }
 
        return 1;
    }
}
 
string sv(int a, int b) {
    int cur, nxt, f=0;
    int num[2]={a, b};
    int bit[NMAX]={0,}, pre[NMAX]={0,};
    queue< int > q;
 
    if(a>0) {
        pre[a%N] = -1; bit[a%N] = a;
        q.push(a%N);
    }
 
    pre[b%N] = -1; bit[b%N] = b;
    q.push(b%N);
 
    while(!q.empty()) {
        cur = q.front();
        q.pop();
 
        if(cur == 0) {
            f = 1;
            break;
        }
 
        for(int k=0;k<2;k++) {
            nxt = (cur*10+num[k])%N;
 
            if(!pre[nxt]) {
                pre[nxt] = cur;
                bit[nxt] = num[k];
                q.push(nxt);
            }
        }
    }
 
    if(f == 0) return "-1";
 
    stack< int > st;
    while(cur != -1) {
        st.push(bit[cur]);
        cur = pre[cur];
    }
 
    string ret;
    while(!st.empty()) {
        ret.push_back(st.top()+'0');
        st.pop();
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> N;
 
    reti = 10;
    for(int i=0;i<10;i++) {
        for(int j=i;j<10;j++) {
            if(!i and !j) continue;
 
            tmp = sv(i, j);
            if(tmp == "-1") continue;
 
            if(i == j) tmpi = 1;
            else tmpi = 2;
 
            // isBig(a, b): a보다 b가 더 크면 true 반환
            if(tmpi<reti or (tmpi==reti and isBig(tmp, ret))) {
                ret = tmp;
                reti = tmpi;
            }
        }
    }
 
    cout << ret;
 
}

 

후기

비둘기집의 원리와 BFS탐색, 그리고 역추적을 사용하는 문제입니다. 나머지를 사용하여 탐색의 범위를 줄이는 방법이 흥미로운 문제입니다. BFS 심화 문제로 추천합니다.