[백준- 4375] 각 자릿수가 모두 1로만 이루어진 n의 배수 중 가장 작은 수

문제
2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

 

# 예제 입력
3
7
9901

# 출력
3
6
12

 

 

처음 이 문제를 보고 도통 이해가 가지 않았다.

"각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는다?"

해당 문장이 말하는 뜻은 n의 배수인데 각 자릿수가 1로만 되어있는 값을 말하는 것이다.

즉 [1, 11, 111, 111, 1111 ∙∙∙] 값들 중 n의 배수를 찾으라는 뜻이다.

 

처음에는 해당 문제가 비교적 간단하다고 생각하였다.

n의 값을 7이라고 가정해보자

 1 % 7 = 1

11 % 7
= ((1 x 10) + 1) % 7
= 4

111 % 7
= ((11 x 10) + 1) % 7
=  6 

1111 % 7
= ((111 x 10) + 1) % 7
= 0

 

위의 식을 보면 일정한 패턴이 있음을 알 수 있다.

1 = 1
11 = 1x10 +1
111 = 11 x 10 + 1
1111 = 111 x 10 + 1

 

즉 (("이전 값" x 10) + 1 ) % n 을 해주면 된다.

// 시간초과
import java.io.*;
import java.util.Scanner;

public class problem4375 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            long num = 1;
            int target = sc.nextInt();
            if (target == 1) {
                System.out.println(1);
                return;
            }
            for (int i = 1; true; i++) {
                num = (num * 10) + 1;
                if (num % target == 0) {
                    System.out.println(i + 1);
                    break;
                }
            }
        }

    }
}

 

결과는 맞게 나온다. 하지만 시간초과로 문제의 요구사항을 맞추지 못해 오답처리가 된다.

 

시간 초과가 나는 이유는 "각 자릿수가 모두 1로만 이루어진 수"가 커지면 커질 수록 시간이 늘어나기 때문이다.

n의 값을 9901으로 가정하자

 

1. 만약 값이111 111 111 111 이라면 integer의 범위를 넘어서는 문제가 있다. (integer의 범위는 -2 147 483 648부터 +2 147 483 647)

2. 값이 커질 수록 연산의 부담이 커진다.

 

시간초과가 일어나는 이유는 2번의 이유가 제일 크다.

 

이후 나머지의 성질을 알 필요가 있다.

1 % 9901 = 1
2 % 9901 = 2
3 % 9901 = 3
.
.
9900 % 9901 = 9900
9901 % 9901 = 0
.
.
19801 % 9901 = 9990
19802 & 9901 = 0

 

즉 나머지 값은 n을 넘을 수 없다.

 

나누는 값이 1,000,000,000 이건 결국 나머지 값은 n보다 낮은 값이라는 뜻이다.

또한 문제의 제약 조건에  (1 ≤ n ≤ 10000) 값이 있기 때문에 어떤 값이 들어오건 나머지 값의 범위는 (1 ≤ n ≤ 10000)이라는 것을 알 수 있다. 즉 나머지 범위는 integer를 넘지 않는다는 뜻이며 나머지 값을 이용한다면 연산의 범위를 대폭 줄일 수 있다.

 

이후 모듈러 규칙을 이용해 기존 연산을 재활용하여 연산과 범위를 줄일 수 있다.

 

모듈러 규칙은 다음과 같다.

x mod n = (x mod n) mod n
(a + b) mod n = (a mod n + b mod n) mod n
(a * b) mod n = (a mod n * b mod n) mod n

 

모듈러 성질
(a + b) mod n = (a mod n + b mod n) mod n
9012에 적용해보자

1 % 9901
= 1

11 % 9901
= ((1 x 10) + 1) % 9901
= ((1 x 10 % 9901) + 1 % 9901) % 9901
= (((1 % 9901 x10) + 1 ) % 9901
= (1 x 10 + 1) % 9901
= 11

111 % 9901
= ((11 x 10) + 1) % 9901
= ((11 % 9901 x 10) + 1 % 9901) % 9901
= ((11 x 10) + 1) % 9901
= 111

1 111 % 9012
= ((111 x 10) + 1) % 9901
= ((111 % 9901 x 10) + 1 % 9901) % 9901
= (1110 + 1) % 9901
= 1111

11 111 % 9901
= ((1111 x 10) + 1) % 9901
= ((1111 % 9901 x 10) + 1 % 9901) % 9901
= (11110 + 1) % 9901
= 1210

111 111 % 9901
= ((11111 x 10) + 1) % 9901
= ((11111%9901 x 10) + 1 % 9901) % 9901
=  ((1210 x 10) + 1) % 9901
= 12101 % 9012
= 2200

여기서 주목해야할 것이
111111 % 9901 = 12101 % 9901
해당 식이 같다는 점이다. 나눠야하는 수의 값은 줄어 들었고 결과는 같아졌다.

1 111 111 % 9901
= ((111 111 x 10) + 1) % 9901
= ((111 111 % 9901 x 10) + 1 % 9901) % 9901
= ((2200 10) + 1) % 9901
= 22001 % 9901
= 2199

여기서 주목해야할 것이
1111111 % 9901 = 22001 % 9901
해당 식이 같다는 점이다. 나눠야하는 수의 값은 줄어 들었고 결과는 같아졌다.

11 111 111 % 9901
= ((1 111 111 x 10) + 1) % 9901
= ((1 111 111 % 9901 x 10) + 1 % 9901) % 9901
= (2199 x 10 + 1) % 9901
= 2189

여기서 주목해야할 것이
11 111 111 % 9012 = 26351 % 9012
해당 식이 같다는 점이다. 나눠야하는 수의 값은 줄어 들었고 결과는 같아졌다.

이 뒤부터는 똑같은 형식임으로 불필요한 식은 생략하겠다.

111 111 111 % 9901
= (2189 x 10 + 1) % 9901
= 2089
여기서 주목해야할 것이
111 111 111 % 9901 = 21891 % 9901
해당 식이 같다는 점이다. 나눠야하는 수의 값은 줄어 들었고 결과는 같아졌다.

1 111 111 111 % 9901
= (2089 x 10  + 1) % 9901
= 1089
1 111 111 111 % 9901 = 20891 % 9901
해당 식이 같다는 점이다. 나눠야하는 수의 값은 줄어 들었고 결과는 같아졌다.

11 111 111 111 % 9901
= (1089 x 10 + 1) % 9901
= 990
11 111 111 111 % 9901 = 10891 % 9901
해당 식이 같다는 점이다. 나눠야하는 수의 값은 줄어 들었고 결과는 같아졌다.

111 111 111 111 % 9901
= (990 x 10 + 1) % 9901
= 0

111 111 111 111 % 9901 = 9901 % 9901
해당 식이 같다는 점이다. 나눠야하는 수의 값은 줄어 들었고 결과는 같아졌다.
나머지가 0인 값을 구하였다.

//개선코드
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int target = sc.nextInt();
            func(target);
        }
    }
    public static void func(int target){
        int num = 1;
        for(int i = 2; true; i++){
            if(target == 1) {
                System.out.println(1);
                return;
            }
            num = (num* 10) + 1;
            num = num % target;
            if(num % target==0) {
                System.out.println(i);
                break;
            }
        }
    }
}