[백준/BOJ] 4375번: 1

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

4375번: 1

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

해설

1로만 이루어진 수 중 가장 작은 n의 배수를 찾아야 한다.

따라서 1을 저장한 변수(temp)를 시작으로 1, 11, 111, . . . . 을 n으로 나눴을 때 가장 먼저 나눠떨어지는 값이 답이 된다.

temp = (temp * 10) + 1

 

하지만 저렇게 자리수를 늘려가며 나누게 되면 시간 초과가 난다.

이를 해결하기 위해 temp를 n으로 나눈 나머지에 10을 곱하고 1을 더해준다.

(실제 나눗셈을 하는 과정을 생각해보자.)

이를 반복하여 0으로 나누어 떨어질 때의 자릿수를 출력하면 된다.

소스 코드

fun main() = with(System.`in`.bufferedReader()) {
    while(true){
        val n = readLine() ?: break
        var temp = 1L
        var cnt = 1
        while(true) {
            if(temp % n.toLong() == 0L) {
                println(cnt)
                break
            }
            temp %= n.toLong()
            temp = (temp * 10) + 1
            cnt++
        }
    }
}