[자바] 백준 4375 - 1 (java)

 문제 : boj4375

---

 

필요 알고리즘 개념

• 브루트포스
  
  • 풀이1의 경우 BigInteger를 사용해 브루트포스로 푼다.
• 수학, 정수론
  
  • 풀이2의 경우 나머지 연산의 특성을 사용해 BigInteger를 사용하지 않고 푼다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 2와 5로 나누어 떨어지지 않는다는 조건이 왜 붙었냐면, 소인수분해시 2와 5가 있을 경우 그 중 작은 수 만큼 수의 낮은 자리수에 0이 생겨서 1로 나누어떨어지지 않게 된다. 즉, 위 조건은 언젠가 1로만 이루어진 n의 배수가 나타나는 것이 보장되었다고 얘기하는 부분이다.

 

 

풀이 1 (코드 1)

  1로만 이루어진 n의 배수는 찾으려면 n의 배수들을 살펴보면서 전부 1로 이루어져있는지 봐야 할 것이다. 하지만 당연히 이건 비효율적이다. 반대로 생각해서 1, 11, 111, 1111, ... 이렇게 1로만 이루어진 수가 n으로 나누어떨어지는걸 찾으면 된다. 그런데 1111111111111111111111111111... 이런 엄청 큰 수까지 봐야 하므로 int나 long으로는 표현이 불가하다. 따라서 엄청 큰 수를 지원하면서도, 나누어떨어지는지 확인 가능한 무언가가 필요하다. 자바의 경우엔 BigInteger가 이걸 해준다. 따라서 BigInteger의 수 1부터 매번 x10+1 을 해서 1 -> 11 -> 111 -> ... 이렇게 증가시켜가면서 나누어떨어지는지 확인해주면 된다.

 

 

풀이 2 (코드 2)

  수학적으로 보면 더 효율적으로 답을 구할 수 있다. (위는 코드1, 아래는 코드2)

 

  우선 나머지 연산의 법칙을 알고 있어야 한다.

 

1111... 이걸 잘 보면 예를들어 1111 = ((10+1)*10+1)*10+1 이고, 그 다음 숫자인 11111은 1111*10+1 이다. 이렇게 매번 곱셈과 덧셈을 해서 다음 수를 찾을 수 있다.

 

그리고 우리가 찾으려고 하는건 111, 1111, 11111... 이런식으로 증가시키다가 1111..%n이 0이 되는 값을 찾는 것이다. 따라서 위 분배법칙을 적용시켜서 매번 %n을 해줘도, 0이 되는 값을 찾는데 문제가 없다는걸 알 수 있다.

 

---

 

코드1 (BigInteger 사용) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = "";
        StringBuilder answer = new StringBuilder();
        while ((s=br.readLine()) != null) {
            BigInteger n = new BigInteger(s);
            BigInteger base = BigInteger.ZERO;
            while(true) {
                base = base.multiply(BigInteger.TEN).add(BigInteger.ONE);
                if (base.mod(n).equals(BigInteger.ZERO)) {
                    answer.append(base.toString().length()).append('\n');
                    break;
                }
            }
        }
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

코드2 (수학적으로 푼거) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        StringBuilder answer = new StringBuilder();
        while ((s=br.readLine()) != null) {
            int n = Integer.parseInt(s);
            int base = 1;
            int cnt = 1;
            while ((base=base%n) != 0) {
                cnt++;
                base = base*10+1;
            }
            answer.append(cnt).append('\n');
        }
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}