백준 4375번 1

<백준 4375번 1 - 마포 코딩박>

사용한 알고리즘: 수학


입력되는 수 n 을 갖고 1, 11, 111, ... 등 1로만 이루어진 가장 작은 n의 배수를 찾는 문제입니다.
문제풀이는 다음과 같습니다.

(1) 기본 생각은 K=1을 시작으로 1, 11, 111, ... 차례로 K 자리수를 늘려 n으로 나누어보는 것입니다.

(2) 이때 자리수를 하나 올려줄때마다 기존의 K를 modulo n 을 취해줘야 시간내에 돌아갑니다.

예를들어 n = 3 이 주어지고 K = 11 이 나누어지지 않아 K = 111을 보는 경우를 생각하면,  11 = 9 + 2 = 2 (mod 3) 이므로 111 = 110 + 1 = 20 +1 = 21 (mod 3) 입니다.