4375.py

stackin·2022년 1월 17일
0

BOJ

목록 보기
1/3
import sys

while True:
    try:
        n: int = int(sys.stdin.readline().rstrip())
        answer = 1
        cnt = 1
        while True:
            if not answer % n:
                break
            answer = (answer % n) * 10 + 1
            cnt += 1

        print(cnt)
    except:
        break

2와 5로 나누어 떨어지지 않는 정수 n이 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 문제였다.
n = 7 일때,
1 % 7 = 1
11 % 7 = 4
111 % 7 = 6
1111 % 7 = 5
11111 % 7 = 2
111111 % 7 = 0
1111111 % 7 = 1 ...
이다.
처음봤을땐 그냥 풀면되는줄 알았는데 보니까 1로 이루어진 수가 점점 커진다는것이 문제였다.
여기서는 나머지를 이용하면 쉽게 풀 수 있었다.
위에서 규칙을 찾아보면
11 % 7 = ((1%7) 10 + 1) % 7
111 % 7 = ((11%7)
10 + 1) % 7 ...
으로 규칙을 찾을 수 있다.

profile
배운것을 기록하자

0개의 댓글