[코딩테스트/ 백준 알고리즘] 4375번 : 1 (자바, Java 풀이)

문제

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

4375번: 1

---

문제 설명

---

문제 풀이

 1로만 이루어진 숫자는 1, 11, 111, 1111, 11111, ... 과 같은 숫자를 말하는 것이다. 이 중에 n의 배수가 되는 수가 몇 자리 수인가를 찾는 문제였다.

 9901이 입력으로 주어진 예제를 보면 출력으로 12가 나온 것을 볼 수 있다. 12자릿수는 천억 대의 숫자이기 때문에 일반적인 자료형으로는 담아낼 수 없다. 때문에 이 문제에서는 수를 직접 만들어내지 말고 간접적으로 표현하라는 소리로 받아들일 수 있다.

 

 이걸 어떻게 표현해야 하는지 규칙성이 바로 보이는 사람도 있겠지만 나처럼 지극히 평범한 머글은 약간의 노력을 하면 쉽게 찾을 수 있다.

• 1 % 7 = 1
• 11 % 7 = {(1 % 7) x 10 + 1) % 7 = (1 x 10 + 1) % 7 = 11 % 7 = 4
• 111 % 7 = {(11 % 7) x 10 + 1} % 7 = (4 x 10 + 1) % 7 = 41  % 7 = 6
• 1111 % 7 = {(111 % 7) x 10 + 1} % 7 = (6 x 10 + 1) % 7 = 61 % 7 = 5
• 11111 % 7 = (5 x 10 + 1) % 7 = 51 % 7 = 2
• 111111 % 7 = (2 x 10 + 1) % 7 = 21 % 7 = 0

현재 수의 나머지 연산 값 =  (그 전 수의 나머지 연산 값 x 10 + 1) % 나누려는 값

으로 간단하게 나타낼 수 있다.

---

코드

import java.util.*;

class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int i = 0;
            int count = 1;

            while(true) {
                i = (i * 10 + 1) % n;
                if(i % n == 0) {
                    System.out.println(count);
                    break;
                }
                else {
                    count++;
                }
            }
        }
    }
}

---

총평

 처음에 생각 없이 덤볐다가 '아.. 이 숫자는 내가 만들 수 없는 숫자구나' 라는 생각이 들어서 처음부터 다시 생각하게 했던 문제다.

 수학을 응용해서 낸 문제는 정말 어렵게 풀거나, 정말 쉽게 풀리거나 둘 중 하나인 거 같다.