[파이썬/python] 백준 - 가지고 노는 1

문제

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

---

문제 설명

1. 자연수 N을 입력받는다.
2. N의 배수 중에서 1만으로 이루어진 수 중에 가장 작은 수의 자릿수를 구한다.
3. 불가능한 경우 -1을 출력한다.

 

---

풀이

1로만 이루어지는 수이기 때문에, N이 2와 5로 나누어지면 해당 수의 배수로는 1로만 이루어지는수를 만들수 없다.

따라서 예외처리를 통해 불가능한 경우의 수를 제거했다.  

1만으로 이루어 지는 수를 찾아야 하는데, 문제에서 최대 자릿 수 제한이 없어서 단순 while문으로 끝까지 찾아봤다.

이론상으로는 시간 제한인 2초 내로 해결되는 것 같은데, 문제는 수의 크기였다. 자릿수가 10만대 이상으로 나오게 되면 수가 너무커지기 때문에 실행 시간은 여유로워도 너무 큰 수로 인해 연산이 느려져서 시간초과가 나는 것 같았다.

따라서 모듈러 연산을 통해 구할 수 있을 것이라고 추론했다.

모듈러 연산에서는 $S_{k+1} % n$일 때 $(S_k * 10 + 1) % n$이 성립하게 된다. 따라서 매 번 자릿수를 늘릴 때마다 해당 연산을 진행하게 되면 숫자의 크기가 N의 최댓값인 $10^6$을 넘지 않게 되므로 문제없이 연산이 가능하다. 

 

1. n % 2 == 0, n % 5 == 0이라면 -1을 출력 후 종료한다.
2. 반복문을 통해 num = 1부터 (num * 10 + 1) % n 연산을 반복하여 자릿수를 늘린다.
   1. 자릿수를 cnt에 저장한다. 
   2. num % n == 0 이라면 반복문을 나와 현재 자릿수를 출력한다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())

if n % 2 == 0 or n % 5 == 0:
    print(-1)
    exit()

num = 1
cnt = 1

while True:
    if num % n == 0:
        break
    num = ((num*10) + 1) % n
    cnt += 1
print(cnt)

 

---

시간복잡도

• 문제의 조건만 가지고는 시간복잡도를 추론하기 힘들다.
• 하지만 최대 $N = 10^6$이기 때문에  임의의 숫자를 N으로 모듈러 연산을 취한다면 나올 수 있는 나머지의 경우의 수는 N개일 것 이다. 따라서 예상을 해보자면 아무리 많아도 $O(N)$의 시간복잡도를 가지지 않을까 싶다..