문제
d(75)=75+7+5=87
n, d(n), d(d(n)) ... 과 같은 무한 수열을 만들 수 있다.
예를 들어 33으로 시작한다면, 33, 39, 51, 57, 69 ...
n을 d(n)의 생성자라고 한다. 위의 수열에서 보면 33이 39의 생성자, 39가 51의 생성자이다. (생성자는 한 개 이상일 수도 있다.)
생성자가 없는 숫자를 '셀프 넘버'라고 한다.
10000 보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하라.
풀이
1. 생성자인지 아닌지 체크할 배열을 생성
2. 생성자인지 아닌지 체크하는 알고리즘
- 1~10000까지의 숫자로 전부 d(n)을 하나씩 만들어주면 셀프 넘버를 구분해낼 수 있다.
=> 1~10000으로 만든 d(n) 중에 셀프 넘버가 아닌 숫자가 빠질 수가 없음.
🙄 처음에는 무한수열을 전부 만들어봐야하나..? 했는데 생각해보니까 그냥 1~10000까지 한 번씩만 d(n)을 만들면 셀프 넘버가 아닌 숫자들이 빠질 수가 없더라고!
풀이 코드
#include<iostream>
using namespace std;
int main(void){
cin.tie(NULL); ios_base::sync_with_stdio(false);
int dn;
int arr[10001]={0,};
for(int i=1;i<=10000;i++)
{
dn=i;
for(int j=i;j>0;j/=10)
dn+=j%10;
if(dn<=10000) //dn의 값이 10000 넘어가면 배열 크기를 넘어가니까 오류, 10000 이하인 경우만 체크해주면 된다.
arr[dn]++;
}
for(int i=1;i<=10000;i++)
{
if(arr[i]==0)
cout<<i<<"\n";
}
}💡 유의한 점!
-
10000이 셀프 넘버는 아니지만 그래도 검사해주기 위해
for(int i=1;i<=10000;i++)로 for문을 만들었다. 이 경우 배열의 크기를arr[10001]로 10000보다 한 칸 늘려줘야 잘못 접근하지 않는다. -
배열의 크기로 넣을 변수 dn이 10000 보다 큰 경우 이 dn이 인덱스로서 배열에 접근할 때, 접근하지 못하도록 막아줘야한다.
-
우리는 1~10000의 모든 d(n)을 만들기 때문에 숫자가 커질 수록 dn이 10000을 넘어간다. 하지만 배열의 크기는 10001 이므로 인덱스가 10000 보다 크면 안된다. (배열 접근 오류)
-
처음에 모르고 dn이 10000보다 큰데 접근했더니
Run-Time Check Failure오류가 발생했다 ;; -
if(dn<=10000)인 경우만arr[dn]++;하도록 조건 지정해주자.
