[swift] 백준 - 4375번: 1

4375번: 1

---

성공 풀이

while let n = readLine(), let num = Int(n) {
    var x = 1, count = 1
    while x % num != 0 {
        x = (x*10+1) % num
        print(x)
        count += 1
    }
    print(count)
}

풀이 키워드

주어진 정수 n의 배수가 1로만 이루어진(1, 11, 11, 111...)숫자가 나올 때, 해당 숫자의 자릿수를 구하면 됩니다.

입력값: n = 7
x = 1
count = 1

while x % n이 0일 때까지 반복 {
	
    x = (x*10+1) % 7
    count += 1
    
    while문이 반복할 때 x에 할당되는 값
    11 % 7 = 4
    41 % 7 = 6
    61 % 7 = 5
    51 % 7 = 2
    21 % 7 = 0
    
    111111일 때 1로만 이루어진 7의 최소 배수가 됨

}

만약 해당 풀이를 모듈러연산으로 풀지 않는다면 x의 값은 Int의 범위를 아득히 넘기 때문에 정확하기 문제를 풀기 위해서는 모듈러 연산이 필요합니다.

참고해야할 모듈러 연산의 공식입니다.

(a + b) mod n = (a mod n + b mod n) mod n
(a * b) mod n = (a mod n * b mod n) mod n

해당 공식을 대입해 while문 안에 있는 x = (x*10+1) % 7을 분석한다면

 1 % 7 == 1
 11 % 7 == (1*10+1)%7 == ((1%7)*10+1)%7
 111 % 7 == (11*10+1)%7 == ((11%7)*10+1)%7
 1111 % 7 == (111*10+1)%7 == ((111%7)*10+1)%7

x가 어떻게 1로이루어진 숫자를 대체할 수 있는지 이해할 수 있습니다.

---