[Python/BOJ] 1612. 가지고 노는 1

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

1612번: 가지고 노는 1

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 이 원숭이는 수를 이리저리 가지고 노는 것을 매우 좋아한다. 그중에서도 1을 가지고 노는 것을 매우매우매우매우매우 좋아한다. 이제 원숭이가 1을 가지고 노는 법을 알아보자.

원숭이는 1만으로 이루어진 수를 매우매우매우매우매우매우매우 좋아한다. 그래서 어떤 자연수 N이 있을 때, N의 배수 중에서 1만으로 이루어진 수가 있을 까 생각하게 되었다. 그리고는 원숭이는 N의 배수 중에서 1만으로 이루어진 수중에 가장 작은 수의 자릿수가 알고 싶어졌다. 하지만 오늘도 역시 멍청한 원숭이는 스스로 계산하지 못하고 여러분에게 도움을 요청했다. 조건에 맞는 가장 작은 수의 자릿수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. N은 1이상 1,000,000이하인 자연수이다.

출력

첫째 줄에 N의 배수 중에 1만으로 이루어진 수 중 가장 작은 수의 자릿수를 출력한다. 불가능한 경우는 -1을 출력한다.

풀이

Code

import sys
input = sys.stdin.readline

def solution(n):
    # 1. 주어진 수가 2나 5로 나눠질 경우
    if n % 2 == 0 or n % 5 == 0 : print(-1)
    # 2. n이 1일 경우
    elif n == 1 : print(1)
    # 3. 이외의 경우
    else :
        # 3-1. 시작값 설정
        x = 1
        # 3-2. 자릿수 변수 설정
        digit = 1
        # 3-3.
        while x != 0 :
            # 값에 다음 자릿수 값을 n으로 나눈 나머지 더하기
            x += (x * 9 + 1) % n
            # x값 재정의
            x %= n
            # 자릿수 값 카운트
            digit += 1
        # 3-4. 결과 출력
        print(digit)

if __name__ == "__main__":
    n = int(input())
    solution(n)