[자바] 백준 1612 - 가지고 노는 1 (java)

목차

문제 : boj1612

 

 

필요 알고리즘

• 수학, 정수론
  
  • 나머지 연산의 성질을 알고 있어야 풀 수 있다.

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

 

 

풀이

  N의 실제 배수를 계산하면서 전부 1로만 이루어져 있는지 확인하는건 상당히 난감하다.

반대로 생각해보자.

결국 1, 11, 111, 1111, .... 이런 수가 결국 N으로 나누어 떨어진다면 N의 배수인거다.

이 경우엔 좀 쉬워진다. 그냥 1, 11, 111, ... 이런 수를 쭉 보다가 N으로 나누어 떨어지는지 확인하면 되는거다.

 

  근데 가장 작은 수의 자릿수가 대체 얼마나 될지 알기가 힘들다. 1000만번 해봐도 N으로 나누어 떨어지지 않으면 멈추겠다? 이건 너무 주먹구구식이다. (이하 내용을 보면 알겠지만, 100만번 해봐도 안되면 거기서 -1 출력해도 정답이긴 하다.)

 

  여기서 1 -> 11 -> 111 -> ... 이렇게 숫자가 커지는 과정은 결국 x10+1 이라고 볼 수 있다.

1*10+1 = 11 -> 11*10+1 = 111 -> ...

이 때 우리가 원하는건 이 수가 N으로 나누어 떨어지는지이다.

그리고 나머지 연산에는 다음과 같은 공식이 성립한다.

 

  즉, 그냥 N으로 나눈 나머지만 유지하더라도 N으로 나누어 떨어지는지 알 수 있다는 얘기이다.

N = 3일 경우를 생각해보자.

1은 3으로 나누어떨어지지 않는다.

1*10+1 = 11은 3으로 나누어떨어지지 않는다. 그리고 3으로 나눈 나머지인 2만 유지하자.

2*10+1 = 21은 3으로 나누어떨어진다. 실제론 이게 111을 확인해본 셈이다. 그러므로 3이 답이다.

 

  이렇게 해도 자릿수가 최대 얼마나 될지 모르는건 마찬가지니 똑같지않을까?

근데 진행하면서 N으로 나눈 나머지가 동일하다면, 사이클이 생긴거다. 이후 계속해서 x10+1을 진행할테니, 이후 다른 수는 나올 수가 없다. 즉, N으로 나눈 나머지가 반복되는 부분이 있다면 그 이후로는 답을 절대 찾을 수 없으니 -1을 출력하고 끝내면 된다.

 

  N으로 나눈 나머지의 종류는 총 N개만 존재한다는 점을 생각해보자. 즉, 총 N개의 나머지 케이스에 대한 방문체크만 해주면 사이클이 생겼는지 알 수 있고, 시간 복잡도는 O(N)으로 답을 구할 수 있다.  

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

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

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int s = 0;
        int cnt = 0;
        Set<Integer> chk = new HashSet<>();
        while (true) {
            cnt++;
            s*=10;
            s+=1;
            s%=n;
            if (s==0) {
                System.out.println(cnt);
                return;
            }
            if (chk.contains(s)) break;
            chk.add(s);
        }
        System.out.println(-1);
    }
}