백준 4375번 1 JAVA

링크텍스트

설명

실제 값을 만들지 않고 나머지만 이용해서 해결하는 게 핵심이다.
1111... 같은 수를 직접 만들면 금방 범위를 초과하므로
길이가 k인 수 111...1을 n으로 나눈 나머지를 반복적으로 갱신한다.
규칙

처음 수는 1 → 나머지 r = 1 % n

다음 수는 자릿수 하나 늘린 111...1 → 수학적으로 r = (r * 10 + 1) % n

나머지가 0이 되면 그때의 길이가 정답
시간복잡도: O(N), 공간복잡도: O(1)

회독

• [ x ] 1회
• 2회
• 3회

코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String line;
        while((line = br.readLine())!=null){
            int n = Integer.parseInt(line);

            int count = 1;
            int mod = 1%n;

            while(mod!=0){
                mod = (mod*10+1)%n;
                count++;
            }

            sb.append(count).append("\n");
        }

        System.out.print(sb);
    }
}

BigInteger 코드

import java.io.*;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String line;

        while((line = br.readLine()) != null){
            int n = Integer.parseInt(line.trim());
            BigInteger modBase = BigInteger.valueOf(n);

            BigInteger num = BigInteger.ONE; // 1
            int count = 1;

            while(!num.mod(modBase).equals(BigInteger.ZERO)){
                // num = num * 10 + 1
                num = num.multiply(BigInteger.TEN).add(BigInteger.ONE);
                count++;
            }

            sb.append(count).append('\n');
        }

        System.out.print(sb);
    }
}