백준 1612번: 가지고 노는 1

문제: https://www.acmicpc.net/problem/1612

문제 풀이

수학, 정수론

num = 1로만 이루어진 수를 N으로 나눈 나머지

count = 현재 1로만 이루어진 수의 자릿수

나눗셈은 자릿수마다 몫과 나머지로 이루어짐

따라서 10의 자릿수에서 나눈 나머지는 1의 자릿수에서 나눠야 하는 값의 10의 자리의 수로 들어감

따라서 num을 1로만 이루어진 수를 N으로 나눈 나머지로 정의하고 초깃값은 0으로 만듬

count는 이 때 N으로 나누는 1로만 이루어진 수의 자릿수이므로 처음 나누는 자릿수는 1이므로 초깃값이 1이 됨

num에 10을 곱하고 1을 더한 이후에 N으로 나눈 나머지를 저장하고 이 num이 0이 된다면 현재 자릿수가 1로만 이루어진 N의 배수 중 가장 작은 수이므로 count를 출력하고 반복문을 탈출함

아니라면 아직 1로만 이루어진 N의 배수를 찾지 못한 것이므로 다음 자릿수를 계산하기 위해 count를 1 증가시킴

그리고 N이 2, 5의 배수라면 N의 배수가 절대로 일의 자리가 1이 될 가능성이 없으므로 1로만 이루어진 N의 배수는 존재할 수 없기 때문에 -1을 출력하면 정답

풀이 설명

N의 배수 중 1로만 이루어진 수 중 가장 작은 수의 자릿수를 구하는 문제이다. 먼저 생각난 방법은 1로만 이루어진 수를 작은 수부터 N으로 나누어 떨어지는지 확인하는 방법이다.

그러나 이는 자릿수가 많아지면 Long의 범위를 넘어설 수 있기 때문에 실제로 만들어서 하는 방법은 쉽지 않다.

그렇기에 다른 방법을 살펴보기 위해 실제로 나누어지는 수를 나누는 과정을 보기로 했다. 111은 3으로 나누어 떨어지는 1로만 이루어진 수이다.

111은 우선 3으로 나눈 몫이 37이 된다. 여기서 37을 자릿수마다 나눠서 따로 곱하면 90과 21을 더한 꼴이 된다. 여기서 111의 앞 두자릿수 11만 3으로 나눈 목과 나머지로 나누면 9와 2가 되고 이는 방금 자릿수마다 따로 곱한 수의 앞자릿수 9와 2가 된다는 사실을 알 수 있다.

즉, 1로 이루어진 수를 N으로 나누는 것은 자릿수마다 이어지기 때문에 여기에 계속 10을 곱하고 1을 더하면 더 큰 자릿수의 1로 이루어진 수를 십의 자릿수까지만 나눈 나머지가 되므로 이 수를 다시 N으로 나누면 이전 자릿수보다 한 자릿수가 많은 1로 이루어진 수를 N으로 나누는 꼴이 된다는 것이다.

따라서 이 방법으로 값이 나누어 떨어질때까지 자릿수를 증가시키면 N의 배수 중 1로만 이루어진 수 중 가장 작은 수를 구할 수 있다.

단, N의 배수 중 끝 자리의 수가 1이 되지 않을 수가 있다. 이런 경우엔 무한 루프를 돌기 때문에 미리 걸러야 한다. 소수 중 끝 자리의 수가 1이 될 수 없는 수가 2, 5가 있으므로 N이 2, 5의 배수라면 N의 배수는 1로만 이루어진 수가 될 수가 없다.

따라서 N을 먼저 2와 5로 나눈 나머지가 0이라면 불가능한 경우이므로 -1, 그게 아니라면 자릿수를 구할때마다 N으로 나눈 나머지에 10을 곱하고 1을 더한 후 다시 N으로 나눈 나머지가 0이 될 때의 자릿수를 출력하면 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    nextToken()
    val N = nval.toInt()
    if(N % 2 == 0 || N % 5 == 0) {
        println(-1)
        return@run
    }
    var num = 0
    var count = 1
    while (true){
        num = (num * 10 + 1) % N
        if(num == 0){
            println(count)
            break
        }
        count++
    }
}