[Algo Rhythm🕺💃] BOJ 4375 - 1

문제 분석

1로만 이루어진 한 정수를 $x$, 2와 5로 나누어 떨어지지 않는 정수를 $n (1 \le n \le 10^5)$이라고 하자.

이 정수의 오른쪽 끝에 1을 붙이기 위해서는 정수의 자릿수를 한 자리 올린 후 1을 더하면 된다. 즉, $10 \times x + 1$을 하면 된다. 하지만 overflow가 발생할 수 있기 때문에 계속해서 오른쪽 끝에 1을 붙일 수 없다.

다행히도 문제에서 요구하는 것은 $x$ 자체가 아니라 $x \mod n == 0$을 만족할 때의 자릿수이다. 따라서, 중요한 것은 $x$가 아니라 $x \mod n$이라는 것을 알 수 있다. 그래서 정수의 오른쪽 끝에 1을 붙일 때 $x = 10 \times x + 1$이 아닌 $x = (10 \times x + 1) \mod n$을 하면 된다. 이를 표현한 수식은 아래와 같다.

 

 

이때 2번째, 3번째 수식은 나머지 연산의 성질을 이용한 것인데 그것들은 아래와 같다.

 

문제 풀이

앞서 언급한 성질을 이용하여 주어진 $n$에 대하여 $x \mod n == 0$을 만족하는 자릿수를 구하고 출력한다.

 

복잡도 분석

1로만 이루어진 한 정수를 $x$, 2와 5로 나누어 떨어지지 않는 정수를 $n (1 \le n \le 10^5)$이라고 할 때, 시간 복잡도와 공간 복잡도는 아래와 같다.

 

⏰ 시간 복잡도 : ???

솔직히 잘 모르겠다. 왜냐하면 $x \mod n == 0$을 만족할 때까지 반복해야 하는데 최악의 경우 얼마나 반복하는지 구하기가 어렵기 때문이다.

🏠 공간 복잡도 : $O(1)$

 

코드

문제 출처

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

4375번: 1