[백준] 4673 - 셀프 넘버

문제 : https://www.acmicpc.net/problem/4673

4673번: 셀프 넘버

 

 

함수 d(n) = m 에서 n을 m의 생성자라고 한다.

 

이때 생성자를 갖지 않는 숫자를 셀프넘버라고 정의하고 있다.

 

즉 셀프넘버는 함수 d 의 정의역인 양의 정수 n을 함수에 대입했을 때 나오지 않는 수를 말한다.

 

간단하게 함수 d 의 치역이 아닌 수를 찾는 문제라고 할 수 있겠다.

 

그런 수들 중 10000 이하의 수를 모조리 찾아야 한다.

 

그런데 d(n) = m 에서 n이 주어지는 경우 m은 간단하게 찾을 수 있지만,

 

m이 주어지는 경우 n을 찾는 것은 어려워 보인다.

 

따라서 나는 두가지 사실을 토대로 문제를 풀려고 한다.

1. d(n) > n
2. 10000 이하의 치역을 모두 찾으면, 치역이 아닌 수는 자동으로 찾게 된다.

 

2번에 의해 m이 주어지는 경우는 가볍게 무시할 수 있게 되었다.

 

이제 10000 이하의 치역을 찾아보자.

 

1번에 의해 나는 d(n)에서 n에 1~10000까지의 수를 모두 대입했을 때의 결과값만 얻으면 된다.

 

따라서 함수 d를 구현해보자.

 

 

d는 큰 어려움 없이 구현할 수 있다.

 

 

main 함수이다.

 

함수 d에 1부터 10000까지의 매개변수를 넘기고, 반환값을 인덱스 사용해서 배열에 -1을 기록한다.

 

만약 한 번도 반환되지 않은 숫자 x 가 있다면 d(x) = 0일 것이다.

 

따라서 배열 n의 원소들 중 그 값이 0인 것들만 출력한다.