[4673] 셀프 넘버

[1. 문제 재정의 및 추상화]

d(n) = n + {n 의 각 자리수의 합}

ex) d(75) = 75 + 7 + 5 = 87

여기서 n 을 d(n) 의 생성자라 하며,

생성자가 없는 숫자를 셀프 넘버라 한다.

ex) 1, 3, 5, 7, 9, ...

 

요구사항
=> 10000보다 작거나 같은 셀프 넘버를 한줄씩 출력해야 함.

 

[2. 해결 계획]

1. 셀프 넘버는 생성자가 없으므로, d(n) 수열에서 가장 처음에 온다 할 수 있다.
2. 계산된 d(n) 은 셀프 넘버가 아니므로, 출력하지 않도록 한다.
3. 10K+1 길이를 갖는 배열을 생성하고, 셀프 넘버인 n 을 index 로 하는 경우 그 값을 0으로하고, 셀프 넘버가 아닌 경우 그 생성자를 저장하도록 한다.

 

[3. 계획 검증]

1. 메모리 제한은 크게 상관 없어 보임
2. d(n) 계산에 대해서 시간 복잡도는 상수시간에 가까움

 

[4. 구현]

package main

import "fmt"

/*func calc_digit_sum(value int) int {
	if value == 0 {
		return value
	}

	return (value % 10) + calc_digit_sum(value/10)
}*/

// 재귀 구현보다 수행 속도가 더 빠름
// 76ms -> 60ms
func calc_digit_sum(value int) int {
	ret := 0
	for value > 0 {
		ret += (value % 10)
		value /= 10
	}

	return ret
}

func calc_self_number(constructor int) int {
	return constructor + calc_digit_sum(constructor)
}

func main() {
	const MAX int = 10001
	var numbers [MAX]int

	for i := 1; i < MAX; i++ {
		if numbers[i] != 0 {
			continue
		}

		constructor := i
		for constructor < MAX {
			new_constructor := calc_self_number(constructor)
			if new_constructor < MAX {
				numbers[new_constructor] = constructor
			}
			constructor = new_constructor
		}

		fmt.Println(i)
	}
}