[B4375] 1

1. 문제 설명

2와 5로 나누어 떨어지지 않는 정수 n이 주어졌을 때, 1로만 이루어진 n의 배수(e.g., 1, 11, 111...)를 찾는 프로그램을 작성하여 그 중 가장 작은 수의 자리수를 출력하시오.

2. 제약 조건

2와 5로 나누어 떨어지지 않는 정수 $n$ 은 $1 ≤ n ≤ 10000$ 을 만족한다.
각 테스트 케이스는 한 줄로 이루어져 있다.

3. 접근

3-1. 정답이 반드시 존재하는지 여부 파악

1, 11, 111, 1111, ...의 규칙을 만족하는 n개의 수가 있다고 가정하자. 1번째부터 n번째까지, 모든 수가 n으로 나누었을 때 서로 나머지가 다르다고 가정하자. 여기서 맨 끝에 하나의 수가 더 추가되어 총 n + 1개의 수가 되면 어떻게 될까? n + 1개의 수들은 n으로 나누었을 때 서로 나머지가 전부 다를 수 있을까?

정답은 그렇지 않다는 것이다. 어떤 수를 n으로 나눈 나머지는 n을 초과할 수 없기 때문이다. 예컨대 n = 9라고 가정하면, 나머지를 0, 1, 2, 3, ..., 9까지 각각 하나씩 가진다고 해도 다 합해서 n개밖에 되지 않기 때문에 n + 1번째 마지막 수는 반드시 저 중에서 하나를 나머지로 가질 수밖에 없다. 이것을 비둘기집의 원리라고 한다. 따라서 n + 1개의 수 중에서, 어떤 두 수는 반드시 n으로 나눈 나머지가 같다.

그리고 그 어떤 두 수가 각각 1111...11과 1111..11이라고 가정할 때, 그 두 수를 뺀 값은 언제나 1111..00의 패턴을 지니며, 나눗셈의 원리에 의해 그 두 수를 뺀 값은 반드시 n의 배수이다. 문제는 1로만 이루어진 n의 배수를 찾고 있으므로, 해당 값을 10...00으로 나누어서 0을 제외하면 문제의 해를 찾을 수 있다.

따라서 1, 11, 111, ... 등의 수를 차례대로 n으로 나누어 나가면, 브루트 포스 방식으로 해를 찾을 수 있음이 증명되었다. 문제는 n의 범위가 1부터 10,000까지이기 때문에, 21자리 수부터는 long long 자료형으로도 연산이 불가능하다는 것이다.

3-2. 나머지 연산의 성질을 이용한 풀이

여기서 등장하는 것이 바로 모듈로 연산이다. 어떤 수가 n의 배수일 경우, 그 수는 n으로 모듈로 연산을 수행했을 때 결과값이 0이 나와야 한다. 즉, 이 문제는 1로만 이루어진 임의의 수 % n == 0이 참인지 묻는 문제다.

그리고 이처럼 정답을 모듈로 연산한 값을 묻는 문제의 경우 중요한 특징이 하나 있는데, 바로 중간해를 모듈로 연산한 값을 정답을 찾는 과정에 활용할 수 있다는 점이다. 모듈로 연산은 아래와 같은 정리를 만족하기 때문이다.

$(A+B)\ mod\ M=((A\ mod\ M)+(B\ mod\ M))\ mod\ M$

$(A×B)\ mod\ M=((A\ mod\ M)×(B\ mod\ M))\ mod\ M$

1, 11, 111, 1111, ...와 같은 규칙으로 증가하는 수는 $(a * 10) + 1$ 와 같은 규칙으로 표현할 수 있으며, 문제는 $(a * 10) + 1 \ mod\ n$ 한 값이 0인지 묻고 있다. 그렇다면 위 정리를 이용해서 해당 수식을 다르게 표현해보도록 하자.

$(a\ *\ 10)+1\ mod\ n$

$= ((a\ *\ 10)\ mod\ n + 1\ mod\ n)\ mod\ n$

$= ((a\ mod\ n) *\ (10\ mod\ n))\ mod\ n + 1\ mod\ n)\ mod\ n$

또한, $(a\ mod\ n) \ mod\ n = a\ mod\ n$ 처럼 $mod$ 연산을 여러 번 수행하는 것은 $mod$ 연산을 한 번 수행하는 것과 같으므로, 마지막 수식은 아래와 같이 바꾸어 쓸 수 있다.

$= ((a\ mod\ n) *10) + 1)\ mod\ n$

여기서 주목해야 하는 부분은 $a\ mod\ n$ 이다. a는 지난 반복(iteration)의 결과값이기 때문에, 지난 반복에서 결과값에 $mod\ n$ 한 값을 이번 반복으로 넘겼다면 $a\ mod\ n$ 은 이번 반복에서 곧바로 파악이 가능하다. 무엇보다 이 방식에서 해당 값은 $n$ 을 초과할 수 없기에, 이번 반복에서 자릿수가 매우 크게 증가하는 것을 방지할 수 있다.

4. 구현

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char** argv) {

	// freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

    int a, n, digit;

    while(cin >> n){

        a = 0; digit = 0;

        while(true){
			
			digit++;
            a = 10 * a + 1;
            if(a % n == 0)
            	break;
            else
				a %= n; // a mod n을 다음 반복으로 넘김
            	
        }
        
        cout << digit << '\n';

    }

	return 0;
}

5. 예외 처리 및 주의사항

이 문제에서 테스트 입력은 한 줄으로 들어온다. 따라서 케이스 하나만 입력받고 답을 출력하는 게 아니라, 케이스가 끝날 때까지 값을 입력받을 수 있도록 while문의 조건을 cin >> n으로 작성한다. (EOF까지 입력받기 위해 while(!cin.eof())로 작성하자 에러를 냈는데, 정확한 이유는 아직 불명이다.)

또한 중간값을 모듈로 연산하여 넘기면, 통상적으로 자릿수를 계산하기 위한 알고리즘인 아래 코드를 사용할 수 없다.

void count_digit(long long n){
	
	int digit = 0;
	
	while(n >= 1){
		digit++;
		n /= 10;	
	}
	
	cout << digit << '\n';
	
}

그 이유는, 중간값이 계속 모듈로 연산되며 자릿수가 n의 최대값인 10,000 미만으로 제한되기 때문이다. 따라서 while문 내에서 다음 반복으로 넘어갈 때마다 digit을 1 증가시켜 주는 방식으로 작성하도록 한다.