PS(Problem Solving)/BOJ

[백준/BOJ] 4375번: 1

JunsuKim 2022. 2. 17.
728x90

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

 

4375번: 1

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

www.acmicpc.net

문제

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을 더해준다.

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

[백준/BOJ] 4375번: 1 - undefined - 해설

이를 반복하여 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++
        }
    }
}
728x90

댓글