8111 0과 1

문제

폴란드 왕자 구사과는 다음과 같은 수를 좋아한다.

• 0과 1로만 이루어져 있어야 한다.
• 1이 적어도 하나 있어야 한다.
• 수의 길이가 100 이하이다.
• 수가 0으로 시작하지 않는다.

예를 들어, 101은 구사과가 좋아하는 수이다.

자연수 N이 주어졌을 때, N의 배수 중에서 구사과가 좋아하는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(T < 10)가 주어진다.

둘째 줄부터 T개의 줄에는 자연수 N이 한 줄에 하나씩 주어진다. N은 20,000보다 작거나 같은 자연수이다.

출력

각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다.

======

문제 분석

0과 1로만 이루어진 수를 N으로 나눴을 때 나머지가 0인 값을 찾으면 되는 문제이다.

이때 나눠야 될 수가 2^100이므로 1부터 전체 탐색을 하다보면 시간초과가 될 것이 분명하다.

규칙을 찾거나 중복 탐지를 통해 탐색을 최소화 할 수 있다면 베스트인 속도가 나올 것이다.

어떠한 수를 N으로 나눴을 때 나머지가 K 라면 그 K를 또 N으로 나눈다면 나머지는 또 K가 나온다

이것은 모듈러 연산의 특징

즉, 수를 체크할 때마다 동일한 나머지가 나오는 것은 아무리 연산을 하더라도 같은 나머지가 나와서 체크하지 않아도 되니 완전 탐색시 중복 방지가 가능해진다.

단, 여기에서 최대 수가 2^100인 만큼 직접적으로 나머지 연산을 진행할 시 수가 커질 경우 정확하지 않은 값이 나오므로 이 또한 모듈러 연산의 특징을 이용하여

const newMod = (mod * 10 + parseInt(digit)) % N; 

이전 연산에서의 나머지 값에 10을 곱한 뒤 0 또는 1의 값을 더해준다. 이 후 그 값을 N으로 나눠서 모듈러 값을 구한다.

const main = (N) => {
    if (N === 1) return '1';

    const queue = [];
    const visited = Array(N).fill(false);

    queue.push({ num: '1', mod: 1 % N });
    visited[1 % N] = true;

    while (queue.length > 0) {
        const { num, mod } = queue.shift();

        if (mod === 0) return num;

        for (const digit of ['0', '1']) {
            const newNum = num + digit;
            const newMod = (mod * 10 + parseInt(digit)) % N;

            if (!visited[newMod]) {
                queue.push({ num: newNum, mod: newMod });
                visited[newMod] = true;
            }
        }
    }
    return 'BRAK';
};
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

input.shift();
const answer = [];

while (input.length) {
    answer.push(main(+input.shift()));
}
console.log(answer.join('\n'));