백준(BOJ) 4375 : 1 (JAVA)

처음엔 1, 11, 111... 이런식으로 수를 늘려가면서 수를 나눠본 후, 처음 나누어 떨어졌을 때의 자리수를 구하면 된다고 생각했다. 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringJoiner;

public class Main {
    public static void main(String[] args) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final StringJoiner result = new StringJoiner(System.lineSeparator());

        String input;
        while ((input = br.readLine()) != null) {
            final int n = Integer.parseInt(input);
            result.add(String.valueOf(computeAnswer(n)));
        }

        System.out.println(result);
    }

    private static int computeAnswer(int n) {
        long multiplyer = 1;
        int count = 1;

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

        return count;
    }
}

하지만 이 코드는 시간초과로 실패했다. 이것 저것 시도를 해보다가 결국 포기하고 구글링을 했다.

 

이 문제는 아래의 나머지 성질을 이용해서 풀 수 있다.

(A + B) % C = (A % C + B % C) % C
(A * B) % C = ((A % C) * (B % C)) % C

이것은 수학 시간에 배우던 분배법칙과 비슷하다. 하지만 '%'라는 기호는 프로그래밍을 하면서 처음 알게되었고 증명이 필요했다.

아... 근데 막상 이 공식을 통해서 어떻게 multiplyer = (multiplyer * 10 + 1) % n 으로 적용해도 된다는 걸 알 수 있는 건지 모르겠다. 아무리 봐도 모르겠네...ㅠ 내가 수학을 하는 건지 코딩을 하고 있는 건지...-_-;; 아무튼 그래서 더 간단한 방법으로 증명하는 건 불가능할까 고민하다가 아래와 같이 증명해봤다.

이렇게 하면, 10A + 1 을 B로 나눴을 때의 나머지가 10R + 1을 B로 나눴을 때의 나머지와 같다는 걸 쉽게 알 수 있다. 비단 10과 1에 국한되진 않을 거다. 아무튼 이 결과를 적용한 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringJoiner;

public class Main {
    public static void main(String[] args) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final StringJoiner result = new StringJoiner(System.lineSeparator());

        String input;
        while ((input = br.readLine()) != null) {
            final int n = Integer.parseInt(input);
            result.add(String.valueOf(computeAnswer(n)));
        }

        System.out.println(result);
    }

    private static int computeAnswer(int n) {
        int multiplyer = 1;
        int count = 1;

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

        return count;
    }
}

 

이 문제를 통해 알게된 정말 놀라운 사실은, 기본형에 해당하는 수의 크기를 줄이는 것으로 속도를 향상시킬 수 있다는 것이었다. 연산에 드는 시간이 줄긴하겠지만, 이렇게나 차이가 날 줄이야...;

 

 

※ 참고 : https://dynamiccube.tistory.com/4