[백준 - JAVA] 4375번 : 1

https://www.acmicpc.net/problem/4375

4375번: 1

 

문제 조건 파악 및 접근

 

문제를 보고 이해하는데 살짝 시간이 걸렸는데 결국 주어진 n의 배수 중에서 1로만 이뤄진 n의 배수를 찾는 문제였다.

 

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

 

 

해당 문제는 나머지 연산의 법칙을 알고 있어야 한다.

 

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

 

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

 

      1 % 7 = 1                                                | n = 7, x = 1  > 11, i = 1 
     11 % 7 =      (1 % 7) x 10 + 1 = 10 + 1 = 11 , 11 % 7 = 4 | n = 7, x = 11 > 41, i = 2 
    111 % 7 =     (11 % 7) x 10 + 1 = 40 + 1 = 41 , 41 % 7 = 6 | n = 7, x = 41 > 61, i = 3
   1111 % 7 =    (111 % 7) x 10 + 1 = 60 + 1 = 61 , 61 % 7 = 5 | n = 7, x = 61 > 51, i = 4
  11111 % 7 =   (1111 % 7) x 10 + 1 = 50 + 1 = 51 , 51 % 7 = 2 | n = 7, x = 51 > 21, i = 5
 111111 % 7 =  (11111 % 7) x 10 + 1 = 20 + 1 = 21 , 21 % 7 = 0 | n = 7, x = 21 >  1, i = 6
1111111 % 7 = (111111 % 7) x 10 + 1 =  0 + 1 =  1              | n = 7, x = 1  >  1

 

 

소스 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String strNum = "";
        while ((strNum = br.readLine()) != null) {
            int n = Integer.parseInt(strNum);
            int onlyOne = 0;
 
            for (int cnt = 1; ; cnt++) {
                onlyOne = (onlyOne * 10 + 1)% n;
 
                if (onlyOne == 0) {
                    System.out.println(cnt);
                    break;
                }
            }
        }
 
        br.close();
    }
}