실버 찍먹



백준_#4673 - 셀프 넘버 | Silver V

d(n) 함수

d(75)라는 수가 있으면 75 + 7 + 5 = 87 이 됨. 자연수 n이 주어졌을때 이 짓을 무한반복 할 수 있음.
n = 10이라고 해보면 10 + 1 + 0 = 11, 11 + 1 + 1 = 13, 13 + 1 + 3 = 17…

생성자

n == 생성자. 위 예시에서 17의 생성자는 13임. 생성자는 한 개보다 많을수도 있고, 아예 없을수도 있음.

셀프 넘버

생성자가 없는 수임. 3을 예시로 들면
1 + 1 = 2, 2 + 2 = 4, 4 + 4 = 8… 이므로 3이 생성될 수 없음.

문제

  • 10000보다 작거나 같은 셀프 넘버를 출력하시오.

n이 셀프넘버인지 아닌지 구분하려면 일단 생성자가 있는지 없는지부터 확인을 해야하는데… 생성자 유무를 어떻게 판단하죠…?
n - n + 1부터 n - 1까지 전부 계산하면 너무 비효율적인데…

1 Like

효율 비효율 이전에… 제한시간인 1초만에 통과할 수 있는가? 를 먼저 따져보심이
물론 효율을 고민하는건 매우 좋습니다

1 Like
C
#include <stdio.h>
#include <stdbool.h>

bool v[10001];

int main() {
	for (int i = 1; i <= 10000; ++i) {
		if (!v[i]) printf("%d\n", i);
        v[i + i % 10 + i / 10 % 10 + i / 100 % 10 + i / 1000 % 10] = true;
	}
	return 0;
}
3 Likes

이 코드 설명점여…

이해 안되는 부분이 어디죠?
짧으니까 스스로 보는것 추천

제가 처음 생각한 방법이,
반복문을 돌면서 배열에 1부터 10000까지 d(n)함수로 계산한 결과값을 저장하고, 또 반복문을 돌아서 그 배열에 없는 수를 출력하는 거였어요.

익명2님은 간단하게 bool 형식의 배열을 만들고 거기에 셀프 넘버가 아닌 숫자만 index에 집어넣어서 true로 만들었네요. 그리고 v[i]true가 아니면 i는 셀프 넘버일테니 출력을 시키면 되네요.
여기서 제가 이해가 안되는건

i + i % 10 + i / 10 % 10 + i / 100 % 10 + i / 1000 % 10
이 수식이 어떻게 d(n)의 결과가 되는가?

입니다. 이해가 될듯 말듯 하네요…

아니 그보다 이런 방법을 어떻게 생각하신건지 이해가 안되는데요;;

이제보니 수식도 조금 이해가 되네요.

i = 46
46 % 10 = 6
46 / 10 % 10 = 4 % 10 = 4

i = 512
512 % 10 = 2
512 / 10 % 10 = 51 % 10 = 1
512 / 100 % 10 = 5 % 10 = 5

i = 8192
8192 % 10 = 2
8192 / 10 % 10 = 819 % 10 = 9
8192 / 100 % 10 = 81 % 10 = 1
8192 / 1000 % 10 = 8 % 10 = 8
1 Like