Kotlin] 백준 4375번 풀이

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

4375번: 1

 

 

이 문제를 되게 쉽게 접근하면

..? 그냥 1씩 문자열로 더한 후 숫자열로 parsing 해서 나머지가 0일 때 까지 무한히 반복한다 <

라고 생각할 수 있는데.. 

반례로 9997을 나눠보면 문제가 발생한다

점점점 늘어나더니 숫자가 infinity값으로 변환되고, 따라서 나머지가 NaN로 리턴된다.

 

따라서, 이 문제는 '어떻게 큰 수를 만들지 않고 나머지를 구할 수 있는가?' 가 관건이다.

이는 모듈로 연산을 활용해야한다.

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

모듈로 연산이란? (개념 이해하기) | 암호학이란? | Khan Academy

 

즉, A mod  B = (A + K * B) mod  B 라는 뜻이다.

예를 들면

11 mod 3 = (1 + 10 * 1) mod 3 과 일치한다는 뜻이다.

111 mod 3 = (1 + 10 * 11) mod 3과 일치한다.

이를 위에 값과 함께 대입해보면

111 mod 3 = (1 + 10 * (1 + 10 * 1)) mod 3과 일치한다.

즉, 처음에 1을 넣고, 이의 나머지를 계속 넣어주면 된다. 

 

이를 코드로 쓰면

fun main(args: Array<String>) {
    question4375()
}

fun question4375() {

    while (true) {

        val numberString = readlnOrNull() ?: break

        val number = numberString.toInt()
        var count = 1
        var oneNumber = 1.0

        if(number % 2 == 0 || number % 5 == 0) {
            continue
        }

        while (true) {
            if(oneNumber % number == 0.0) {
                break
            } else {
                oneNumber = (oneNumber * 10 + 1) % number
                count++
            }
        }

        println("${count}")

    }

}

 

(보통 다른 문제들은 입력의 끝을 알려주는 게 많았는데, 이 문제는 입력 끝에 대한 언급이 없어 어떻게 줘야 하나 고민하느라 포인터 에러가 많이 난 것 같습니다)