[백준] 4673: 셀프 넘버 - Swift

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

 

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 

 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 

 

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97. 10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

• 입력: 없음

• 출력: 10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

---

풀이

var s: Set<Int> = []
for i in 1...10000 {
    s.insert(d(i))
}
for j in 1...10000 {
    if !s.contains(j) { print(j) }
}
func d(_ n:Int) -> Int {
    var sum = n, now = n
    while now != 0 {
        sum += now%10
        now /= 10
    }
    return sum
}

1부터 10000까지의 숫자에 각각 d(n)을 적용하여 Set에 모아둔 다음, 거기에 속하지 않는 숫자만 프린트하는 풀이.

이렇게 풀어야지 생각한 이후로 코드 쓰는 건 어렵지 않았는데, 규칙이 있을까봐서 고민을 오래했다. 

 

 

다음은 그 고민의 과정.

 

 

예제 출력에 나와 있는 셀프 넘버의 예시들로 직접 계산을 해보았다.

 

규칙 찾아보려 노력한 흔적. 이거 하면서 스페이스바 두번 치면 자동 마침표가 생성되는 기능을 드디어 껐다.

 

다른 숫자들은 일부 패턴이 겹치는 것 외엔 뚜렷한 패턴이 없는데,

9에서 시작하여 d(n)을 계속 적용하면 9 -> 18 -> 27 -> 36... 계속 9의 배수가 이어진다.

즉, 9의 배수라면 셀프 넘버가 될 수 없다.

 

또한 9 -> 20 -> 31 -> 42 -> 53...처럼 9에서부터 11씩 더한 수는 모두 셀프 넘버이며, 

예제 출력에서 9903 -> 9914 -> 9925 -> 9927 -> 9938...로 이어지는데, 9925에서 11 더했을 때 나오는 9936이 마침 또 9의 배수. 그래서 9925 다음엔 9936에서 9를 뺀 9927이 이어지고 다시 11씩 차이가 나는 것을 보고...

for i in 1...9 {
    if !i.isMultiple(of: 2) { print(i) }
}

var numberNow = 9

while numberNow <= 10000 {
    numberNow += 11
    if numberNow % 9 != 0 {
        print(numberNow)
    } else {
        numberNow -= 9
        print(numberNow)
    }
}

위의 패턴을 구현해보았지만... 시원하게 오답😅

 

패턴이 정말 없는 게 맞겠지..?