[백준 C++] 4994 배수 찾기

문제

양의 정수 n이 주어졌을 때, n의 배수 중에서 0과 1로만 이루어진 m을 찾는 프로그램을 작성하시오. n은 200을 넘지 않고, m은 0보다 큰 양의 정수이며, 100자리를 넘지 않아야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄에는 n (1 ≤ n ≤ 200)이 주어진다. 입력의 마지막 줄에는 0이 주어진다.

출력

입력으로 주어지는 각각의 n마다 m을 출력한다. m의 길이는 100을 넘지 않으며, 가능한 경우가 여러 가지라면 아무거나 출력한다.

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

풀이

결과적으로 N의 배수로 M을 만드는것인데,
M은 0 과 1로만 이루어져있다고한다.
그럼 M이 될 수 있는지 0과 1을 이용해서 만들어보고
맞으면 출력하면된다.
가장처음수는 1 로부터
0을 붙여보고 %N 확인, 1을 붙여보고 %N 확인 이걸 반복하는데 큐와같은 자료구조를 이용해서
정보를 저장하고 빼내야 같은길이를 같은 M을 탐색하므로, 혹시나 M의 길이가 작은경우 프로그램이 무한반복되며 끝나지않는 오류? 가 없을것이다.

접근만 잘하면 생각보다 쉬운 개념이기에 코드만 올리겠다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector; using std::stack; using std::queue;
using std::deque; using std::string; using std::pair;
using std::sort;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, char> pic;
typedef pair<char, int> pci;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef pair<string, string> pss;

int N = 200;
void func() {
    queue<ll> q;
    scanf("%d", &N);
    while (N) {
        q.push(1);
        while (!q.empty()) {
            ll num = q.front();
            //printf(">>>> %lld mod %d = %d\n", num, N, num % N);
            if (num % N == 0) {
                printf("%lld\n", num);
                break;
            }
            else {
                q.push(num * 10);
                q.push(num * 10 + 1);
                q.pop();
            }

        }
        while (!q.empty()) q.pop();
        scanf("%d", &N); //다음 수를 받아들임.
    }
}

int main(void) {
    func();

    return 0;
}